Congratulations!

[Valid RSS] This is a valid RSS feed.

Recommendations

This feed is valid, but interoperability with the widest range of feed readers could be improved by implementing the following recommendations.

Source: http://ericniebler.com/feed/

  1. <?xml version="1.0" encoding="UTF-8"?><rss version="2.0"
  2. xmlns:content="http://purl.org/rss/1.0/modules/content/"
  3. xmlns:wfw="http://wellformedweb.org/CommentAPI/"
  4. xmlns:dc="http://purl.org/dc/elements/1.1/"
  5. xmlns:atom="http://www.w3.org/2005/Atom"
  6. xmlns:sy="http://purl.org/rss/1.0/modules/syndication/"
  7. xmlns:slash="http://purl.org/rss/1.0/modules/slash/"
  8. xmlns:georss="http://www.georss.org/georss"
  9. xmlns:geo="http://www.w3.org/2003/01/geo/wgs84_pos#"
  10. >
  11.  
  12. <channel>
  13. <title>Eric Niebler</title>
  14. <atom:link href="http://ericniebler.com/feed/" rel="self" type="application/rss+xml" />
  15. <link>https://ericniebler.com</link>
  16. <description>Judge me by my C++, not my WordPress</description>
  17. <lastBuildDate>Thu, 15 Feb 2024 02:09:29 +0000</lastBuildDate>
  18. <language>en-US</language>
  19. <sy:updatePeriod>
  20. hourly </sy:updatePeriod>
  21. <sy:updateFrequency>
  22. 1 </sy:updateFrequency>
  23. <generator>https://wordpress.org/?v=6.4.3</generator>
  24.  
  25. <image>
  26. <url>https://ericniebler.com/wp-content/uploads/2020/10/favicon-150x150.jpg</url>
  27. <title>Eric Niebler</title>
  28. <link>https://ericniebler.com</link>
  29. <width>32</width>
  30. <height>32</height>
  31. </image>
  32. <site xmlns="com-wordpress:feed-additions:1">155530815</site> <item>
  33. <title>What are Senders Good For, Anyway?</title>
  34. <link>https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=what-are-senders-good-for-anyway</link>
  35. <comments>https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/#comments</comments>
  36. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  37. <pubDate>Mon, 05 Feb 2024 07:46:42 +0000</pubDate>
  38. <category><![CDATA[concurrency]]></category>
  39. <category><![CDATA[coroutines]]></category>
  40. <category><![CDATA[generic-programming]]></category>
  41. <guid isPermaLink="false">https://ericniebler.com/?p=3174</guid>
  42.  
  43. <description><![CDATA[Some colleagues of mine and I have been working for the past few years to give C++ a standard async programming model. That effort has resulted in a proposal, P2300, that has been design-approved for C++26. If you know me <a class="more-link" href="https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/">Continue reading <span class="screen-reader-text">  What are Senders Good For, Anyway?</span><span class="meta-nav">&#8594;</span></a>]]></description>
  44. <content:encoded><![CDATA[<p>Some colleagues of mine and I have been working for the past few years to give C++ a standard async programming model. That effort has resulted in a proposal, <a href="https://wg21.link/p2300">P2300</a>, that has been design-approved for C++26. If you know me or if you follow me on social media, you know I&#8217;m <em>embarrassingly excited</em> about this work and its potential impact. I am aware, however, that not everybody shares my enthusiasm. I hear these things a lot these days:</p>
  45. <blockquote>
  46. <p>Why would I want to use it?</p>
  47. <p>Why do we need senders when C++ has coroutines?</p>
  48. <p>It&#8217;s all just too complicated!</p>
  49. </blockquote>
  50. <p>The P2300 crew have collectively done a <em>terrible</em> job of making this work accessible. At the heart of P2300 is a simple, elegant (IMHO) core that brings many benefits, but it&#8217;s hard to see that forest for all the trees.</p>
  51. <p>So let&#8217;s make this concrete. In this post, I&#8217;ll show how to bring a crusty old C-style async API into the world of senders, and why you might want to do that.</p>
  52. <h1>C(lassic) async APIs</h1>
  53. <p>In a past life I did a lot of Win32 programming. Win32 has several async models to choose from, but the simplest is the good ol&#8217; callback. Async IO APIs like <a href="https://learn.microsoft.com/en-us/windows/win32/api/fileapi/nf-fileapi-readfileex"><code>ReadFileEx</code></a> are shaped like this:</p>
  54. <pre class="brush: cpp; notranslate">/// Old-style async C API with a callback
  55. /// (like Win32's ReadFileEx)
  56.  
  57. struct overlapped {
  58.  // ...OS internals here...
  59. };
  60.  
  61. using overlapped_callback =
  62.  void(int status, int bytes, overlapped* user);
  63.  
  64. int read_file(FILE*, char* buffer, int bytes,
  65.              overlapped* user, overlapped_callback* cb);
  66. </pre>
  67. <p>The protocol is pretty simple: you call <code>read_file</code> passing in the usual arguments plus two extra: a pointer to an &#8220;<code>overlapped</code>&#8221; structure and a callback. The OS will use the <code>overlapped</code> struct for its own purposes, but the user can stuff data there too that the callback can later use. It looks like this:</p>
  68. <pre class="brush: cpp; notranslate">struct my_overlapped : overlapped {
  69.  // ... my extra data goes here ...
  70. };
  71.  
  72. void my_callback(int status, int bytes, overlapped* data) {
  73.  auto* my_data = static_cast&lt;my_overlapped*&gt;(data);
  74.  
  75.  // ...use the extra stuff we put in the `my_overlapped`
  76.  //   object...
  77.  
  78.  delete my_data; // clean up
  79. }
  80.  
  81. void enqueue_read(FILE* pfile) {
  82.  // Allocate and initialize my_data...
  83.  auto* my_data =
  84.    new my_overlapped{{}, /* my data goes here */ };
  85.  
  86.  int status =
  87.    read_file(pfile, buff, bytes, my_data, my_callback);
  88.  // ...
  89. }
  90. </pre>
  91. <p>What happens is this: <code>read_file</code> causes the OS to enqueue an IO operation, saving the <code>overlapped</code> and <code>overlapped_callback</code> pointers with it. When the IO completes, the OS invokes the callback, passing in the pointer to the <code>overlapped</code> struct. I&#8217;ve written code like this hundreds of times. You probably have too.</p>
  92. <p>It&#8217;s simple. It works. Why make this more complicated, right?</p>
  93. <h1>C(onfusion of) async APIs</h1>
  94. <p>There&#8217;s nothing wrong with the callback API. What&#8217;s wrong is that every library that exposes asynchrony uses a <em>slightly different</em> callback API. If you want to chain two async operations from two different libraries, you&#8217;re going to need to write a bunch of glue code to map <em>this</em> async abstraction to <em>that</em> async abstraction. It&#8217;s the Tower of Babel problem.</p>
  95. <blockquote>
  96. <p><img decoding="async" src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Pieter_Bruegel_the_Elder_-_The_Tower_of_Babel_%28Vienna%29_-_Google_Art_Project.jpg/800px-Pieter_Bruegel_the_Elder_-_The_Tower_of_Babel_%28Vienna%29_-_Google_Art_Project.jpg" alt="Pieter Brueghel the Elder, Public domain, via Wikimedia Commons" /> <sup>Pieter Brueghel the Elder, Public domain, via Wikimedia Commons</sup></p>
  97. <p>&#8220;Look, they are one people, and they have all one language, and this is only the beginning of what they will do; nothing that they propose to do will now be impossible for them. Come, let us go down and confuse their language there, so that they will not understand one another&#8217;s speech.&#8221; <sup>— Genesis 11:6–7</sup></p>
  98. </blockquote>
  99. <p>So, when there are too many incompatible ways to do a thing, what do we do? We make another of course.</p>
  100. <blockquote>
  101. <p><img decoding="async" src="https://imgs.xkcd.com/comics/standards.png" alt="xkcd comic about how standards proliferate" /> <sup><a href="https://xkcd.com/927/">https://xkcd.com/927/</a></sup></p>
  102. </blockquote>
  103. <p>The way to escape this trap is for the C++ standard to endorse <strong>one</strong> async abstraction. Then all the libraries that expose asynchrony can map their abstractions to the standard one, and we&#8217;ll all be able to talk to each other. Babel solved.</p>
  104. <p>So that is why the C++ Standardization Committee is interested in this problem. Practically speaking, it&#8217;s a problem that can only be solved by the standard.</p>
  105. <h1>C(omposable) async APIs</h1>
  106. <p>Which brings us to <em>senders</em>, the topic of P2300. There&#8217;s a lot I could say about them (they&#8217;re efficient! they&#8217;re structured! they compose!), but instead I&#8217;m going to show some code and let the code do the talking.</p>
  107. <p>If we look at the <code>read_file</code> API above, we can identify some different parts:</p>
  108. <ol>
  109. <li>The <em>allocation</em> of any resources the async operation needs,</li>
  110. <li>The <em>data</em> that must live at a stable address for the duration of the operation (i.e., the <code>overlapped</code> structure),</li>
  111. <li>The <em>initiation</em> of the async operation that enqueues the async IO, and the handling of any initiation failure,</li>
  112. <li>The user-provided <em>continuation</em> that is executed after the async operation completes (i.e., the callback).</li>
  113. <li>The <em>reclamation</em> of any resources allocated in step 1.</li>
  114. </ol>
  115. <p>Senders have all these pieces too, but in a uniform shape that makes it possible to work with them generically. In fact, the only meaningful difference between senders and the C-style API is that instead of one callback, in senders there are three: one each for success, failure, and cancellation.</p>
  116. <h2>Step 1: The Allocation</h2>
  117. <p>Our re-imagined <code>read_file</code> API will look like this:</p>
  118. <pre class="brush: cpp; notranslate">read_file_sender
  119.  async_read_file(FILE* file, char* buffer, int size)
  120.  {
  121.    return {file, buffer, size};
  122.  }
  123. </pre>
  124. <p>The only job of this function is to put the arguments into a sender-shaped object, which looks as follows (explanation after the break)<sup>[*]</sup>:</p>
  125. <p><small>[*]: Or rather, it <em>will</em> look like this after <a href="https://wg21.link/P2855">P2855</a> is accepted.</small></p>
  126. <pre class="brush: cpp; notranslate">namespace stdex = std::execution;
  127.  
  128. struct read_file_sender
  129. {
  130.  using sender_concept = stdex::sender_t;             // (1)
  131.  
  132.  using completion_signatures =                       // (2)
  133.    stdex::completion_signatures&lt;
  134.      stdex::set_value_t( int, char* ),
  135.      stdex::set_error_t( int ) &gt;;
  136.  
  137.  auto connect( stdex::receiver auto rcvr )           // (3)
  138.  {
  139.    return read_file_operation{{}, {}, pfile, buffer,
  140.                               size, std::move(rcvr)};
  141.  }
  142.  
  143.  FILE* pfile;
  144.  char* buffer;
  145.  int size;
  146. };
  147. </pre>
  148. <p>The job of a sender is to describe the asynchronous operation. (It is also a factory for the operation state, but that&#8217;s step 2.) On the line marked &#8220;(1)&#8221;, we declare this type to be a sender. On the line marked &#8220;(2)&#8221;, we declare the ways in which this asynchronous operation can complete. We do this using a list of function types. This:</p>
  149. <pre class="brush: cpp; notranslate">stdex::set_value_t( int, char* )
  150. </pre>
  151. <p>&#8230; declares that this async operation may complete successfully by passing an <code>int</code> and a <code>char*</code> to the <em>value</em> callback. (Remember, there are three callbacks.) And this:</p>
  152. <pre class="brush: cpp; notranslate">stdex::set_error_t( int )
  153. </pre>
  154. <p>&#8230; declares that this async operation may complete in error by passing an <code>int</code> to the <em>error</em> callback. (If this async operation were cancelable, it would declare that with <code>stdex::set_stopped_t()</code>.)</p>
  155. <h2>Step 2: The Data</h2>
  156. <p>On the line marked &#8220;(3)&#8221; above, the <code>connect</code> member function accepts a &#8220;receiver&#8221; and returns an &#8220;operation state&#8221;. A <em>receiver</em> is an amalgamation of three callbacks: value, error, and stopped (canceled, more or less). The result of connecting a sender and a receiver is an <em>operation state</em>. The operation state, like the <code>overlapped</code> struct in the C API, is the data for async operation. It must live at a stable address for the duration.</p>
  157. <p>The <code>connect</code> function returns a <code>read_file_operation</code> object. The caller of <code>connect</code> assumes responsibility for ensuring that this object stays alive and doesn&#8217;t move until one of the callbacks is executed. The <code>read_file_operation</code> type looks like this (explanation after the break):</p>
  158. <pre class="brush: cpp; notranslate">struct immovable {
  159.  immovable() = default;
  160.  immovable(immovable&amp;&amp;) = delete;
  161. };
  162.  
  163. template &lt;class Receiver&gt;
  164. struct read_file_operation : overlapped, immovable // (1)
  165. {
  166.  static void _callback(int status, int bytes,     // (2)
  167.                        overlapped* data)
  168.  {
  169.    auto* op =
  170.      static_cast&lt;read_file_operation*&gt;(data);     // (3)
  171.  
  172.    if (status == OK)
  173.      stdex::set_value(std::move(op-&gt;rcvr),        // (4)
  174.                       bytes, op-&gt;buffer);
  175.    else
  176.      stdex::set_error(std::move(op-&gt;rcvr),
  177.                       status);
  178.  }
  179.  
  180.  void start() noexcept                            // (5)
  181.  {
  182.    int status =
  183.      read_file(pfile, buffer, size, this, &amp;_callback);
  184.  
  185.    if (status != OK)
  186.      stdex::set_error(std::move(rcvr), status);
  187.  }
  188.  
  189.  FILE* pfile;
  190.  char* buffer;
  191.  int size;
  192.  Receiver rcvr;
  193. };
  194. </pre>
  195. <p>The operation state stores the arguments needed to initiate the async operation as well as the receiver (the three callbacks). Let&#8217;s break this down by line.</p>
  196. <ul>
  197. <li>&#8220;(1)&#8221;: The operation state inherits from <code>overlapped</code> so we can pass a pointer to it into <code>read_file</code>. It also inherits from an <code>immovable</code> struct. Although not strictly necessary, this ensures we don&#8217;t move the operation state by accident.</li>
  198. <li>&#8220;(2)&#8221;: We define the <code>overlapped_callback</code> that we will pass to <code>read_file</code> as a class <code>static</code> function.</li>
  199. <li>&#8220;(3)&#8221;: In the callback, we down-cast the <code>overlapped</code> pointer back into a pointer to the <code>read_file_operation</code> object.</li>
  200. <li>&#8220;(4)&#8221;: In the callback, we check the <code>status</code> to see if the operation completed successfully or not, and we call <code>set_value</code> or <code>set_error</code> on the receiver as appropriate.</li>
  201. <li>&#8220;(5)&#8221;: In the <code>start()</code> function &#8212; which all operation states must have &#8212; we actually initiate the read operation. If the initiation fails, we pass the error to the receiver immediately since the callback will never execute.</li>
  202. </ul>
  203. <h2>Step 3: The Initiation</h2>
  204. <p>You&#8217;ll notice that when we call the sender-ified <code>async_read_file</code> function, we are just constructing a sender. No actual work is started. Then we call <code>connect</code> with a receiver and get back an operation state, but <em>still</em> no work has been started. We&#8217;ve just been lining up our ducks, making sure everything is in place at a stable address so we can initiate the work. Work isn&#8217;t initiated until <code>.start()</code> is called on the operation state. Only then do we make a call to the C-style <code>read_file</code> API, thereby enqueuing an IO operation.</p>
  205. <p>All this hoop-jumping becomes important once we start building pipelines and task graphs of senders. Separating the launch of the work from the construction of the operation state lets us aggregate <em>lots</em> of operation states into one that contains all the data needed by the entire task graph, swiveling everything into place before any work gets started. That means we can launch lots of async work with complex dependencies with only a single dynamic allocation or, in some cases, no allocations at all.</p>
  206. <p>Now I have to fess up. I fibbed a little when I said that the caller of <code>connect</code> needs to keep the operation state alive at a stable address until one of the callbacks is executed. That only becomes true once <code>.start()</code> has been called on it. It is perfectly acceptable to connect a sender to a receiver and then drop the operation state on the floor <em>as long as <code>.start()</code> hasn&#8217;t been called yet</em>. But with <code>.start()</code> you&#8217;re committed. <code>.start()</code> launches the rockets. There&#8217;s no calling them back.</p>
  207. <p>OK, we&#8217;ve constructed the operation state, and we&#8217;ve called <code>.start()</code> on it. Now the proverbial ball is in the operating system&#8217;s court.</p>
  208. <h2>Step 4: The Continuation</h2>
  209. <p>The operating system does its IO magic. Time passes. When the IO operation is finished, it will invoke the <code>_callback</code> function with a status code, a pointer to the <code>overlapped</code> struct (our <code>read_file_operation</code>) and, if successful, the number of bytes read. The <code>_callback</code> passes the completion information to the receiver that was <code>connect</code>-ed to the sender, and the circle is complete.</p>
  210. <p>But wait, what about &#8220;Step 5: Deallocation&#8221;? We never really allocated anything in the first place! The <code>connect</code> function returned the operation state by value. It&#8217;s up to the caller of <code>connect</code>, whoever that is, to keep it alive. They may do that by putting it on the heap, in which case they are responsible for cleaning it up. Or, if this async operation is part of a task graph, they may do that by aggregating the operation state into a larger one.</p>
  211. <h2>Step 6: Profit!</h2>
  212. <p>At this point you may be wondering what&#8217;s the point to all of this. Senders and receivers, operation states with fiddly lifetime requirements, <code>connect</code>, <code>start</code>, three different callbacks &#8212; who wants to manage all of this? The C API was way simpler. It&#8217;s true! So why am I so unreasonably excited about all of this?</p>
  213. <blockquote>
  214. <p>The caller of <code>async_read_file</code> doesn&#8217;t need to care about any of that.</p>
  215. </blockquote>
  216. <p>The end user, the caller of <code>async_read_file</code>, is not going to be mucking about with receivers and operation states. They are going to be awaiting senders in coroutines. Look! The following code uses a coroutine task type from the <a href="https://github.com/NVIDIA/stdexec">stdexec</a> library.</p>
  217. <pre class="brush: cpp; notranslate">exec::task&lt; std::string &gt; process_file( FILE* pfile )
  218. {
  219.  std::string str;
  220.  str.resize( MAX_BUFFER );
  221.  
  222.  auto [bytes, buff] =
  223.    co_await async_read_file(pfile, str.data(), str.size());
  224.  
  225.  str.resize( bytes );
  226.  co_return str;
  227. }
  228. </pre>
  229. <p>What wizardry is this? We wrote a sender, not an awaitable, right? But this is working code! See for yourself: <a href="https://godbolt.org/z/1rjsxWxh7">https://godbolt.org/z/1rjsxWxh7</a>.</p>
  230. <p>This is where we get to reap the benefits of programming to a standard async model. Generic code, whether from the standard library or from third party libraries, will work with our senders. In the case above, the <code>task&lt;&gt;</code> type from the stdexec library knows how to await anything that looks like a sender. If you have a sender, you can <code>co_await</code> it without doing any extra work.</p>
  231. <p>P2300 comes with a small collection of generic async algorithms for common async patterns &#8212; things like chaining (<code>then</code>), dynamically picking the next task (<code>let_value</code>), grouping senders into one (<code>when_all</code>), and blocking until a sender is complete (<code>sync_wait</code>). It&#8217;s a paltry set to be sure, but it will grow with future standards. And as third party libraries begin to adopt this model, more and more async code will work together. Some day very soon you&#8217;ll be able to initiate some file IO, read from the network, wait on a timer, listen for a cancellation from the user, wait for them all to complete, and then transfer execution to a thread pool to do more work &#8212; whew! &#8212; even if each sender and the thread pool came from different libraries.</p>
  232. <h2>Senders, FTW!</h2>
  233. <p>So, back to those pernicious questions folks keep asking me.</p>
  234. <blockquote>
  235. <p>Why would I want to use it?</p>
  236. </blockquote>
  237. <p>You want to use senders because then you can stitch your async operations together with other operations from other libraries using generic algorithms from still other libraries. And so you can <code>co_await</code> your async operations in coroutines without having to write an additional line of code.</p>
  238. <blockquote>
  239. <p>Why do we need senders when C++ has coroutines?</p>
  240. </blockquote>
  241. <p>I hope you realize by now that this isn&#8217;t an either/or. <em>Senders are part of the coroutine story.</em> If your library exposes asynchrony, then returning a sender is a great choice: your users can await the sender in a coroutine if they like, or they can avoid the coroutine frame allocation and use the sender with a generic algorithm like <code>then()</code> or <code>when_all()</code>. The lack of allocations makes senders an especially good choice for embedded developers.</p>
  242. <blockquote>
  243. <p>It&#8217;s all just too complicated!</p>
  244. </blockquote>
  245. <p>I&#8217;ll grant that <em>implementing</em> senders is more involved than using ordinary C-style callbacks. But <em>consuming</em> senders is as easy as typing <code>co_await</code>, or as simple as passing one to an algorithm like <code>sync_wait()</code>. Opting in to senders is opting into an ecosystem of reusable code that will grow over time.</p>
  246. <p>THAT is why I&#8217;m excited about senders.</p>
  247. <p>(And be honest, was wrapping <code>read_file</code> in a sender really all that hard, after all?)</p>
  248. <div style="display:none">
  249. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  250. </div>
  251. ]]></content:encoded>
  252. <wfw:commentRss>https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/feed/</wfw:commentRss>
  253. <slash:comments>7</slash:comments>
  254. <post-id xmlns="com-wordpress:feed-additions:1">3174</post-id> </item>
  255. <item>
  256. <title>Asynchronous Stacks and Scopes</title>
  257. <link>https://ericniebler.com/2021/08/29/asynchronous-stacks-and-scopes/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=asynchronous-stacks-and-scopes</link>
  258. <comments>https://ericniebler.com/2021/08/29/asynchronous-stacks-and-scopes/#comments</comments>
  259. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  260. <pubDate>Sun, 29 Aug 2021 17:07:08 +0000</pubDate>
  261. <category><![CDATA[Uncategorized]]></category>
  262. <guid isPermaLink="false">https://ericniebler.com/?p=3161</guid>
  263.  
  264. <description><![CDATA[In Structured Concurrency, I talk about what structured concurrency is and why it&#8217;s a big deal for C++ especially. In this post I discuss some more interesting properties of asynchronous code that is structured: async stacks and async scopes. Structured <a class="more-link" href="https://ericniebler.com/2021/08/29/asynchronous-stacks-and-scopes/">Continue reading <span class="screen-reader-text">  Asynchronous Stacks and Scopes</span><span class="meta-nav">&#8594;</span></a>]]></description>
  265. <content:encoded><![CDATA[<p>In <a href="https://ericniebler.com/2020/11/08/structured-concurrency/">Structured Concurrency</a>, I talk about what structured concurrency is and why it&#8217;s a big deal for C++ especially. In this post I discuss some more interesting properties of asynchronous code that is structured: async stacks and async scopes.</p>
  266. <h2>Structured concurrency</h2>
  267. <p>Concurrency is <em>structured</em> when &#8220;callee&#8221; async functions complete before their &#8220;caller&#8221; functions resume. This can be done without blocking a thread: the caller (parent) launches the callee (child) task and passes it a handle to itself, effectively telling the child, &#8220;When you have your result, call me back. Until then, I&#8217;m going to sleep.&#8221;</p>
  268. <p>Immediately after the parent launches the child, the parent function does an ordinary return, often to something like an event loop that is churning through async tasks.</p>
  269. <h2>Async stacks</h2>
  270. <p>When we talk about parent/child async tasks, we are talking about a <em>notional</em> caller/callee relationship: there is a sequence of async operations that has caused the current one to be executing. This chain of operations is <em>exactly</em> like a call stack, but asynchronous. The actual program stack will look nothing like it.</p>
  271. <p>Anyone who has debugged a multithreaded application knows that the actual program stack doesn&#8217;t really tell you what you want to know: <em>How did I get here?</em> All it generally shows is that some event loop is currently processing a certain function. The notional async stack tells you <em>why</em>. From the PoV of the event loop, async work is getting scheduled onto it willy-nilly. The <em>structure</em> of the async computation is a higher-level property of your program&#8217;s execution.</p>
  272. <p>Or it isn&#8217;t, as often is the case in multithreaded C++ applications written today. Until C++20, C++ provided no language support for writing structured async code, and so that code is typically <em>unstructured</em>: no parent/child relationships exist at all. Work is scheduled with fire-and-forget semantics, using ad hoc out-of-band mechanisms to synchronize work, propagate values and errors, and keep data alive. It&#8217;s like programming with <code>jmp</code> instructions instead of functions &#8212; no stack at all.</p>
  273. <h2>Async scopes</h2>
  274. <p>C++ programmers have simply accepted this state of affairs because they didn&#8217;t have anything better. Until C++20 introduced coroutines, that is. Coroutines are transformative, not because the syntax is nice, but because <em>they cause <strong><em>async scopes</em></strong> to coincide with lexical scopes</em>.</p>
  275. <p>What&#8217;s an async scope? If an async stack is a chain of async function activations, then an async scope corresponds to the activation of a single async function. It encompasses all the state &#8212; variables and whatnot &#8212; that need to live for the duration of an async operation <em>and all of its nested child operations</em>. With callbacks, the async scope spans disjoint lexical scopes: it starts when an async function is called and ends when the <em>callback</em> returns &#8212; that is, if your code is structured.</p>
  276. <p>If your async code is unstructured, there are no async scopes at all because there&#8217;s no notion of child operations that nest within parents. Or you could say there are overlapping scopes. Unsurprisingly, this makes resource management hard, which is why so much async C++ is littered with <code>std::shared_ptr</code>.</p>
  277. <h2>Coroutines</h2>
  278. <p>Which brings us back to coroutines. For coroutines, the async scope starts when the coroutine is first called and it ends when the coroutine returns (or <code>co_return</code>s I should say). Well, that&#8217;s just like ordinary functions with ordinary scopes! Which is exactly the point.</p>
  279. <p>Forget that coroutines make async code read like synchronous code. Forget that the syntax is nice. The overwhelming benefit of coroutines in C++ is its ability to make your async scopes line up with lexical scopes because now we get to leverage everything we already know about functions, scopes, and resource management. Do you need some piece of data to live as long as this async operation? No problem. Make it a local variable in a coroutine.</p>
  280. <h2>Beyond coroutines&#8230;</h2>
  281. <p>Coroutines make the idea of structured concurrency obvious by manifesting it in code. We don&#8217;t have to worry about <em>notional</em> stacks and scopes.<sup id="fnref:1"><a href="#fn:1" rel="footnote">1</a></sup> There&#8217;s the scope right there, between the curly braces! Here&#8217;s the mindbender though: Just as Dorothy could have gone home to Kansas any time she wanted, so too could we have been structuring our async code all along.</p>
  282. <p>Here&#8217;s a dirty secret about coroutines: they&#8217;re just sugar over callbacks; everything after the <code>co_await</code> in a coroutine is a callback. The compiler makes it so. And damn, we&#8217;ve had callbacks <em>forever</em>, we&#8217;ve just been misusing them. Structured concurrency has been just three heel-clicks away all this time.</p>
  283. <p>Language support makes it <em>much</em> easier to ensure that child operations nest within parents, but with the right library abstractions, structured concurrency in C++ is totally possible without coroutines &#8212; and damn efficient.</p>
  284. <p>Next post, I&#8217;ll introduce these library abstractions, which are the subject of the C++ standard proposal <a href="http://wg21.link/P2300">P2300</a>, and what the library abstractions bring over and above C++20 coroutines.</p>
  285. <div class="footnotes">
  286. <hr />
  287. <ol>
  288. <li id="fn:1">
  289. <p>Well, actually we still do until debuggers grok coroutines and can let us view the async stack.&#160;<a href="#fnref:1" rev="footnote">&#8617;</a></p>
  290. </li>
  291. </ol>
  292. </div>
  293. ]]></content:encoded>
  294. <wfw:commentRss>https://ericniebler.com/2021/08/29/asynchronous-stacks-and-scopes/feed/</wfw:commentRss>
  295. <slash:comments>5</slash:comments>
  296. <post-id xmlns="com-wordpress:feed-additions:1">3161</post-id> </item>
  297. <item>
  298. <title>Structured Concurrency</title>
  299. <link>https://ericniebler.com/2020/11/08/structured-concurrency/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=structured-concurrency</link>
  300. <comments>https://ericniebler.com/2020/11/08/structured-concurrency/#comments</comments>
  301. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  302. <pubDate>Mon, 09 Nov 2020 04:02:48 +0000</pubDate>
  303. <category><![CDATA[concurrency]]></category>
  304. <category><![CDATA[coroutines]]></category>
  305. <guid isPermaLink="false">https://ericniebler.com/?p=3117</guid>
  306.  
  307. <description><![CDATA[TL;DR: &#8220;Structured concurrency” refers to a way to structure async computations so that child operations are guaranteed to complete before their parents, just the way a function is guaranteed to complete before its caller. This sounds simple and boring, but <a class="more-link" href="https://ericniebler.com/2020/11/08/structured-concurrency/">Continue reading <span class="screen-reader-text">  Structured Concurrency</span><span class="meta-nav">&#8594;</span></a>]]></description>
  308. <content:encoded><![CDATA[<p>TL;DR: <strong>&#8220;Structured concurrency” refers to a way to structure async computations so that child operations are guaranteed to complete before their parents, just the way a function is guaranteed to complete before its caller.</strong> This sounds simple and boring, but in C++ it&#8217;s anything but. Structured concurrency — most notably, C++20 coroutines — has profound implications for the correctness and the simplicity of async architecture. It brings the <a href="https://docs.microsoft.com/en-us/cpp/cpp/welcome-back-to-cpp-modern-cpp?view=msvc-160">Modern C++ style</a> to our async programs by making async lifetimes correspond to ordinary C++ lexical scopes, eliminating the need for reference counting to manage object lifetime.</p>
  309. <h2>Structured Programming and C++</h2>
  310. <p>Back in the 1950&#8217;s, the nascent computing industry discovered structured programming: that high-level programming languages with lexical scopes, control structures, and subroutines resulted in programs that were far easier to read, write, and maintain than programming at the assembly level with test-and-jump instructions and <code>goto</code>. The advance was such a quantum leap that nobody talks about structured programming anymore; it&#8217;s just &#8220;programming”.</p>
  311. <p>C++, more so than any other language, leverages structured programming to the hilt. The semantics of object lifetime mirror — and are tied to — the strict nesting of scopes; i.e., the <em>structure</em> of your code. Function activations nest, scopes nest, and object lifetimes nest. Objects&#8217; lifetimes end with a scope&#8217;s closing curly brace, and objects are destroyed in the reverse order of their construction to preserve the strict nesting.</p>
  312. <p>The Modern C++ programming style is built on this structured foundation. Objects have <em>value semantics</em> — they behave like the ints — and resources are cleaned up in destructors deterministically, which guarantees structurally that resources aren&#8217;t used after their lifetimes have ended. This is <em>very</em> important.</p>
  313. <p>When we abandon this strict nesting of scopes and lifetimes — say, when we reference count an object on the heap, or when we use the singleton pattern — we are fighting against the strengths of the language rather than working with them.</p>
  314. <h2>The Trouble With Threads</h2>
  315. <p>Writing correct programs in the presence of concurrency is far more difficult than in single-threaded code. There are lots of reasons for this. One reason is that threads, like singletons and dynamically allocated objects, scoff at your puny nested scopes. Although you can use the Modern C++ style <em>within</em> a thread, when logic and lifetimes are scattered across threads, the hierarchical structure of your program is lost. The tools we use to manage complexity in single-threaded code — in particular, nested lifetimes tied to nested scopes — simply don&#8217;t translate to async code.</p>
  316. <p>To see what I mean, let&#8217;s look at what happens when we take a simple synchronous function and make it asynchronous.</p>
  317. <pre class="brush: cpp; notranslate">void computeResult(State &amp; s);
  318.  
  319. int doThing() {
  320.  State s;
  321.  computeResult(s);
  322.  return s.result;
  323. }
  324. </pre>
  325. <p><code>doThing()</code> is simple enough. It declares some local state, calls a helper, then returns some result. Now imagine that we want to make both functions async, maybe because they take too long. No problem, let&#8217;s use Boost futures, which support continuation chaining:</p>
  326. <pre class="brush: cpp; notranslate">boost::future&lt;void&gt; computeResult(State &amp; s);
  327.  
  328. boost::future&lt;int&gt; doThing() {
  329.  State s;
  330.  auto fut = computeResult(s);
  331.  return fut.then(
  332.    [&amp;](auto&amp;&amp;) { return s.result; }); // OOPS
  333. }
  334. </pre>
  335. <p>If you&#8217;ve programmed with futures before, you&#8217;re probably screaming, <em>&#8220;Nooooo!”</em> The <code>.then()</code> on the last line queues up some work to run after <code>computeResult()</code> completes. <code>doThing()</code> then returns the resulting future. The trouble is, when <code>doThing()</code> returns, the lifetime of the <code>State</code> object ends, <em>and the continuation is still referencing it</em>. That is now a dangling reference, and will likely cause a crash.</p>
  336. <p>What has gone wrong? Futures let us compute with results that aren&#8217;t available yet, and the Boost flavor lets us chain continuations. But the continuation is a separate function with a separate scope. We often need to share data across those separate scopes. No more tidy nested scopes, no more nested lifetimes. We have to manage the lifetime of the state manually, something like this:</p>
  337. <pre class="brush: cpp; notranslate">boost::future&lt;void&gt;
  338. computeResult(shared_ptr&lt;State&gt; s); // addref
  339.                                    // the state
  340.  
  341. boost::future&lt;int&gt; doThing() {
  342.  auto s = std::make_shared&lt;State&gt;();
  343.  auto fut = computeResult(s);
  344.  return fut.then(
  345.    [s](auto&amp;&amp;) { return s.result; }); // addref
  346.                                       // the state
  347. }
  348. </pre>
  349. <p>Since both async operations refer to the state, they both need to share responsibility to keep it alive.</p>
  350. <p>Another way to think about this is: <em>what is the lifetime of this asynchronous computation?</em> It starts when <code>doThing()</code> is called, but it doesn&#8217;t end until the continuation — the lambda passed to <code>future.then()</code> — returns. <em>There is no lexical scope that corresponds to that lifetime.</em> And that is the source of our woes.</p>
  351. <h2>Unstructured Concurrency</h2>
  352. <p>The story gets more complicated yet when we consider executors. Executors are handles to executions contexts that let you schedule work onto, say, a thread or thread pool. Many codebases have some notion of an executor, and some let you schedule things with a delay or with some other policy. This lets us do cool things, like move a computation from an IO thread pool to a CPU thread pool, or retry an async operation with a delay. Handy, but like <code>goto</code> it is a very low-level control structure that tends to obfuscate rather than clarify.</p>
  353. <p>For instance, I recently came across an algorithm that uses executors and callbacks (called Listeners here) that retries the async allocation of some resource. Below is a greatly abridged version. It is described after the break.</p>
  354. <pre class="brush: cpp; notranslate">// This is a continuation that gets invoked when
  355. // the async operation completes:
  356. struct Manager::Listener : ListenerInterface {
  357.  shared_ptr&lt;Manager&gt; manager_;
  358.  executor executor_;
  359.  size_t retriesCount_;
  360.  
  361.  void onSucceeded() override {
  362.    /* ...yay, allocation succeeded... */
  363.  }
  364.  void onFailed() override {
  365.    // When the allocation fails, post a retry
  366.    // to the executor with a delay
  367.    auto alloc = [manager = manager_]() {
  368.      manager-&gt;allocate();
  369.    };
  370.    // Run "alloc" at some point in the future:
  371.    executor_.execute_after(
  372.      alloc, 10ms * (1 &lt;&lt; retriesCount_));
  373.  }
  374. };
  375.  
  376. // Try asynchronously allocating some resource
  377. // with the above class as a continuation
  378. void Manager::allocate() {
  379.  // Have we already tried too many times?
  380.  if (retriesCount_ &gt; kMaxRetries) {
  381.    /* ...notify any observers that we failed */
  382.    return;
  383.  }
  384.  
  385.  // Try once more:
  386.  ++retriesCount_;
  387.  allocator_.doAllocate(
  388.    make_shared&lt;Listener&gt;(
  389.      shared_from_this(),
  390.      executor_,
  391.      retriesCount_));
  392. }
  393. </pre>
  394. <p>The <code>allocate()</code> member function first checks to see if the operation has already been retried too many times. If not it calls a helper <code>doAllocate()</code> function, passing in a callback to be notified on either success or failure. On failure, the handler posts deferred work to the executor, which will call <code>allocate()</code> back, thus retrying the allocation with a delay.</p>
  395. <p>This is a heavily stateful and rather circuitous async algorithm. The logic spans many functions and several objects, and the control and data flow is not obvious. Note the intricate ref-counting dance necessary to keep the objects alive. Posting the work to an executor makes it even harder. Executors in this code have no notion of continuations, so errors that happen during task execution have nowhere to go. The <code>allocate()</code> function can&#8217;t signal an error by throwing an exception if it wants any part of the program to be able to recover from the error. Error handling must be done manually and out-of-band. Ditto if we wanted to support cancellation.</p>
  396. <p>This is <strong>unstructured concurrency</strong>: we queue up async operations in an <em>ad hoc</em> fashion; we chain dependent work, use continuations or &#8220;strand” executors to enforce sequential consistency; and we use strong and weak reference counts to keep data alive until we are certain it&#8217;s no longer needed. There is no formal notion of task A being a child of task B, no way to enforce that child tasks complete before their parents, and no one place in the code that we can point to and say, &#8220;Here is the algorithm.&#8221;</p>
  397. <blockquote>
  398. <p><strong>If you don&#8217;t mind the analogy, the hops through the executor are a bit like <code>goto</code> statements that are non-local in both time and space: &#8220;Jump to this point in the program, <em>X</em> milliseconds from now, on this particular thread.&#8221;</strong></p>
  399. </blockquote>
  400. <p>That non-local discontinuity makes it hard to reason about correctness and efficiency. Scale unstructured concurrency up to whole programs handling lots of concurrent real-time events, and the incidental complexity of manually handling out-of-band asynchronous control and data flow, controlling concurrent access to shared state, and managing object lifetime becomes overwhelming.</p>
  401. <h2>Structured Concurrency</h2>
  402. <p>Recall that in the early days of computing, unstructured programming styles rapidly gave way to structured styles. With the addition of coroutines to C++, we are seeing a similar phase shift happening today to our asynchronous code. If we were to rewrite the above retry algorithm in terms of coroutines (using Lewis Baker&#8217;s popular <a href="https://github.com/lewissbaker/cppcoro">cppcoro</a> library), it might look something like this:</p>
  403. <pre class="brush: cpp; notranslate">// Try asynchronously allocating some resource
  404. // with retry:
  405. cppcoro::task&lt;&gt; Manager::allocate() {
  406.  // Retry the allocation up to kMaxRetries
  407.  // times:
  408.  for (int retriesCount = 1;
  409.       retriesCount &lt;= kMaxRetries;
  410.       ++retriesCount) {
  411.    try {
  412.      co_await allocator_.doAllocate();
  413.      co_return; // success!
  414.    } catch (...) {}
  415.  
  416.    // Oops, it failed. Yield the thread for a
  417.    // bit and then retry:
  418.    co_await scheduler_.schedule_after(
  419.      10ms * (1 &lt;&lt; retriesCount));
  420.  }
  421.  
  422.  // Error, too many retries
  423.  throw std::runtime_error(
  424.    "Resource allocation retry count exceeded.");
  425. }
  426. </pre>
  427. <blockquote>
  428. <p>Aside: This replaces the <code>executor_</code> with a <code>scheduler_</code> that implements cppcoro&#8217;s <a href="https://github.com/lewissbaker/cppcoro#delayedscheduler-concept">DelayedScheduler</a> concept.</p>
  429. </blockquote>
  430. <p>Let&#8217;s list the ways in which this is an improvement:</p>
  431. <ol>
  432. <li>It&#8217;s all in one function! Good locality.</li>
  433. <li>The state (like <code>retriesCount</code>) can be maintained in local variables instead of as members of objects that need to be ref-counted.</li>
  434. <li>We can use ordinary C++ error handling techniques.</li>
  435. <li>We are guaranteed structurally that the async call to <code>allocator_.doAllocate()</code> completes before this function continues executing.</li>
  436. </ol>
  437. <p>Point (4) has profound implications. Consider the trivial example from the beginning of the article. The following re-implementation in terms of coroutines is perfectly safe:</p>
  438. <pre class="brush: cpp; notranslate">cppcoro::task&lt;&gt; computeResult(State &amp; s);
  439.  
  440. cppcoro::task&lt;int&gt; doThing() {
  441.  State s;
  442.  co_await computeResult(s);
  443.  co_return s.result;
  444. }
  445. </pre>
  446. <p>The above code is safe because we know that <code>computeResult</code> completes before <code>doThing</code> is resumed and thus before <code>s</code> is destructed.</p>
  447. <blockquote>
  448. <p><strong>With structured concurrency, it is perfectly safe to pass local variables by reference to child tasks that are immediately awaited.</strong></p>
  449. </blockquote>
  450. <h2>Cancellation</h2>
  451. <p>Taking a structured approach to concurrency, where the lifetime of concurrent operations is strictly nested within the lifetime of resources that it uses and is tied to program scopes, allows us to avoid needing to use garbage collection techniques like <code>shared_ptr</code> to manage lifetime. This can lead to code that is more efficient, requiring fewer heap-allocations and fewer atomic reference-counting operations, as well as code that is easier to reason about and is less bug-prone. However, one implication of this approach is that it means that we must always join and wait for child operations before the parent operation can complete. We can no longer just detach from those child operations and let the resources get cleaned up automatically when their ref-counts drop to zero. To avoid having to wait unnecessarily long times for child operations whose results are no longer needed, we need a mechanism to be able to cancel those child operations so that they complete quickly. Thus the structured concurrency model requires deep support for cancellation to avoid introducing unnecessary latency.</p>
  452. <p>Note that we rely on structured lifetime and structured concurrency every time we pass a local variable to a child coroutine by reference. We must ensure that the child coroutine has completed and is no longer using that object before the parent coroutine exits the scope of that local variable and destroys it.</p>
  453. <h2>Structured Concurrency > Coroutines</h2>
  454. <p>When I talk about &#8220;structured concurrency,” I am not just talking about coroutines — although that is its most obvious manifestation. To see what I mean, let&#8217;s talk briefly about what coroutines <em>are</em> and what they <em>are not</em>. In particular, there is nothing inherently concurrent about C++ coroutines at all! They are really just a way to get the compiler to carve your function up into callbacks for you.</p>
  455. <p>Consider the simple coroutine above:</p>
  456. <pre class="brush: cpp; notranslate">cppcoro::task&lt;&gt; computeResult(State &amp; s);
  457.  
  458. cppcoro::task&lt;int&gt; doThing() {
  459.  State s;
  460.  co_await computeResult(s);
  461.  co_return s.result;
  462. }
  463. </pre>
  464. <p>What does <code>co_await</code> here mean? The trite answer is: it means whatever the author of <code>cppcoro::task&lt;&gt;</code> wants it to mean (within certain bounds). The fuller answer is that <code>co_await</code> suspends the current coroutine, bundles up the rest of the coroutine (here, the statement <code>co_return s.result;</code>) as a continuation, and passes it to the awaitable object (here, the <code>task&lt;&gt;</code> returned by <code>computeResult(s)</code>). That awaitable will typically store it somewhere so it can be invoked later, when the child task completes. That&#8217;s what <code>cppcoro::task&lt;&gt;</code> does, for instance.</p>
  465. <p>In other words, the <code>task&lt;&gt;</code> type and the coroutines language feature conspire together to layer &#8220;structured concurrency” on top of boring ol&#8217; callbacks. That&#8217;s it. That&#8217;s the magic. It&#8217;s all just callbacks, but callbacks in a very particular pattern, and it is that pattern that makes this &#8220;structured.” The pattern ensures that child operations complete before parents, and that property is what brings the benefits.</p>
  466. <p>Once we recognize that structured concurrency is really just callbacks in a particular pattern, we realize that we can achieve structured concurrency <em>without coroutines</em>. Programming with callbacks is nothing new, of course, and the patterns can be codified into a library and made reusable. That&#8217;s what <a href="https://github.com/facebookexperimental/libunifex">libunifex</a> does. If you follow C++ standardization, it is also what the sender/receiver abstraction from <a href="http://wg21.link/P0443">the Executors proposal</a> does.</p>
  467. <p>Using libunifex as a basis for structured concurrency, we can write the example above as follows:</p>
  468. <pre class="brush: cpp; notranslate">unifex::any_sender_of&lt;&gt; computeResult(State &amp; s);
  469.  
  470. auto doThing() {
  471.  return unifex::let_with(
  472.    // Declare a "local variable" of type State:
  473.    [] { return State{}; },
  474.    // Use the local to construct an async task:
  475.    [](State &amp; s) {
  476.      return unifex::transform(
  477.        computeResult(s),
  478.        [&amp;] { return s.result; });
  479.    });
  480. }
  481. </pre>
  482. <p>Why would anybody write that when we have coroutines? You would certainly need a good reason, but I can think of a few. With coroutines, you have an allocation when a coroutine is first called, and an indirect function call each time it is resumed. The compiler can sometimes eliminate that overhead, but sometimes not. By using callbacks directly — but in a structured concurrency pattern — we can get many of the benefits of coroutines without the tradeoffs.</p>
  483. <p>That style of programming makes a different tradeoff, however: it is far harder to write and read than the equivalent coroutine. I think that >90% of all async code in the future should be coroutines simply for maintainability. For hot code, selectively replace coroutines with the lower-level equivalent, and let the benchmarks be your guide.</p>
  484. <h2>Concurrency</h2>
  485. <p>I mention above that coroutines aren&#8217;t inherently concurrent; they&#8217;re just a way of writing callbacks. Coroutines are inherently sequential in nature and the laziness of <code>task&lt;&gt;</code> types — where a coroutine starts suspended and doesn&#8217;t start executing until it is awaited — means that we can&#8217;t use it to introduce concurrency in the program. Existing <code>future</code>-based code often assumes that the operation has already started eagerly, introducing <em>ad hoc</em> concurrency that you need to be careful to prune back. That forces you to re-implement concurrency patterns over and over in an <em>ad hoc</em> fashion.</p>
  486. <p>With structured concurrency, we codify concurrency patterns into reusable algorithms to introduce concurrency in a structured way. For instance, if we have a bunch of <code>task</code>s and would like to wait until they have all completed and return their results in a <code>tuple</code>, we pass them all to the <code>cppcoro::when_all</code> and <code>co_await</code> the result. (Libunifex also has a <code>when_all</code> algorithm.)</p>
  487. <p>At present, neither cppcoro nor libunifex has a <code>when_any</code> algorithm, so you can&#8217;t launch a bunch of concurrent operations and return when the <em>first</em> one completes. It&#8217;s a very important and interesting foundational algorithm, though. To maintain the guarantees of structured concurrency, when the first child task completes, <code>when_any</code> should request cancellation on all the other tasks <em>and then wait for them all to finish</em>. The utility of this algorithm depends upon all async operations in your program responding promptly to cancellation requests, which demonstrates just how important deep support for cancellation is in modern async programs.</p>
  488. <h2>Migration</h2>
  489. <p>So far, I&#8217;ve discussed what structured concurrency is and why it matters. I haven&#8217;t discussed how we get there. If you are already using coroutines to write async C++, then congrats. You may keep enjoying the benefits of structured concurrency, perhaps with a deeper understanding and appreciation for <em>why</em> coroutines are so transformative.</p>
  490. <p>For codebases that lack structured concurrency, deep support for cancellation, or maybe even an abstraction for asynchrony, the job is hard. It may even start with <em>introducing</em> complexity in order to carve out an island in which the surrounding code provides the guarantees that structured concurrency patterns require. This includes, for instance, creating the <em>impression</em> of prompt cancellation of scheduled work, even when the underlying execution contexts don&#8217;t offer that directly. That added complexity can be isolated in a layer, and the islands of structured concurrency can be built on top. Then the simplifying work can begin, taking future- or callback-style code and converting them to coroutines, teasing out parent/child relationships, ownership, and lifetime.</p>
  491. <h2>Summary</h2>
  492. <p>Adding <code>co_await</code> makes a synchronous function asynchronous, without disturbing the structure of the computation. The async operation being awaited necessarily completes before the calling function does, just like ordinary function calls. The revolution is: <em>nothing changes</em>. Scopes and lifetimes still nest as they always have, except now the scopes are discontinuous in time. With raw callbacks and futures, that structure is lost.</p>
  493. <p>Coroutines, and structured concurrency more generally, bring the advantages of the Modern C++ style — value semantics, algorithm-driven design, clear ownership semantics with deterministic finalization — into our async programming. It does that because it ties async lifetimes back to ordinary C++ lexical scopes. Coroutines carve our async functions up into callbacks at suspension points, callbacks that get called in a very specific pattern to maintain that strict nesting of scopes, lifetimes, and function activations.</p>
  494. <p>We sprinkle <code>co_await</code> in our code and we get to continue using all our familiar idioms: exceptions for error handling, state in local variables, destructors for releasing resources, arguments passed by value or by reference, and all the other hallmarks of good, safe, and idiomatic Modern C++.</p>
  495. <p>Thanks for reading.</p>
  496. <hr />
  497. <p><em>If you want to hear more about structured concurrency in C++, be sure to check out <a href="https://www.youtube.com/watch?v=1Wy5sq3s2rg">Lewis Baker&#8217;s CppCon talk</a> from 2019 about it.</em></p>
  498. <div style="display:none">
  499. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  500. </div>
  501. ]]></content:encoded>
  502. <wfw:commentRss>https://ericniebler.com/2020/11/08/structured-concurrency/feed/</wfw:commentRss>
  503. <slash:comments>28</slash:comments>
  504. <post-id xmlns="com-wordpress:feed-additions:1">3117</post-id> </item>
  505. <item>
  506. <title>Standard Ranges</title>
  507. <link>https://ericniebler.com/2018/12/05/standard-ranges/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=standard-ranges</link>
  508. <comments>https://ericniebler.com/2018/12/05/standard-ranges/#comments</comments>
  509. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  510. <pubDate>Thu, 06 Dec 2018 01:58:12 +0000</pubDate>
  511. <category><![CDATA[generic-programming]]></category>
  512. <category><![CDATA[library-design]]></category>
  513. <category><![CDATA[ranges]]></category>
  514. <category><![CDATA[std]]></category>
  515. <category><![CDATA[std2]]></category>
  516. <guid isPermaLink="false">http://ericniebler.com/?p=1058</guid>
  517.  
  518. <description><![CDATA[As you may have heard by now, Ranges got merged and will be part of C++20. This is huge news and represents probably the biggest shift the Standard Library has seen since it was first standardized way back in 1998. <a class="more-link" href="https://ericniebler.com/2018/12/05/standard-ranges/">Continue reading <span class="screen-reader-text">  Standard Ranges</span><span class="meta-nav">&#8594;</span></a>]]></description>
  519. <content:encoded><![CDATA[<p>As you may have heard by now, Ranges got merged and will be part of C++20. This is huge news and represents probably the biggest shift the Standard Library has seen since it was first standardized way back in 1998.</p>
  520. <p>This has been a long time coming. Personally, I&#8217;ve been working toward this since at least November 2013, when I opined, &#8220;<em>In my opinion, it’s time for a range library for the modern world</em>,&#8221; in a <a href="http://ericniebler.com/2013/11/07/input-iterators-vs-input-ranges/">blog post on input ranges</a>. Since then, I&#8217;ve been busy building that <a href="https://github.com/ericniebler/range-v3">modern range library</a> and nailing down <a href="http://wg21.link/P0896">its specification</a> with the help of some <a href="https://twitter.com/CoderCasey">very talented people</a>.</p>
  521. <p>Future blog posts will discuss how we got here and the gritty details of how the old stuff and the new stuff play together (we&#8217;re C++ programmers, we love gritty details), but this post is strictly about the <em>what</em>.</p>
  522. <h1>What is coming in C++20?</h1>
  523. <p>All of the Ranges TS — <em>and then some</em> — will ship as part of C++20. Here&#8217;s a handy table of all the major features that will be shipping as part of the next standard:</p>
  524. <table>
  525. <thead>
  526. <tr>
  527. <th>Feature</th>
  528. <th>Example</th>
  529. </tr>
  530. </thead>
  531. <tbody>
  532. <tr>
  533. <td>Fundamental concepts</td>
  534. <td><code>std::Copyable&lt;T&gt;</code></td>
  535. </tr>
  536. <tr>
  537. <td>Iterator and range concepts</td>
  538. <td><code>std::InputIterator&lt;I&gt;</code></td>
  539. </tr>
  540. <tr>
  541. <td>New convenience iterator traits</td>
  542. <td><code>std::iter_value_t&lt;I&gt;</code></td>
  543. </tr>
  544. <tr>
  545. <td>Safer range access functions</td>
  546. <td><code>std::ranges::begin(rng)</code></td>
  547. </tr>
  548. <tr>
  549. <td>Proxy iterator support</td>
  550. <td><code>std::iter_value_t&lt;I&gt; tmp =</code><br />&nbsp;&nbsp;&nbsp;&nbsp;<code>std::ranges::iter_move(i);</code></td>
  551. </tr>
  552. <tr>
  553. <td>Contiguous iterator support</td>
  554. <td><code>std::ContiguousIterator&lt;I&gt;</code></td>
  555. </tr>
  556. <tr>
  557. <td>Constrained algorithms</td>
  558. <td><code>std::ranges::sort(v.begin(), v.end());</code></td>
  559. </tr>
  560. <tr>
  561. <td>Range algorithms</td>
  562. <td><code>std::ranges::sort(v);</code></td>
  563. </tr>
  564. <tr>
  565. <td>Constrained function objects</td>
  566. <td><code>std::ranges::less</code></td>
  567. </tr>
  568. <tr>
  569. <td>Generalized callables</td>
  570. <td><code>std::ranges::for_each(v, &amp;T::frobnicate);</code></td>
  571. </tr>
  572. <tr>
  573. <td>Projections</td>
  574. <td><code>std::ranges::sort(employees, less{},</code><br />&nbsp;&nbsp;&nbsp;&nbsp;<code>&amp;Employee::id);</code></td>
  575. </tr>
  576. <tr>
  577. <td>Range utilities</td>
  578. <td><code>struct my_view : std::view_interface&lt;my_view&gt; {</code></td>
  579. </tr>
  580. <tr>
  581. <td>Range generators</td>
  582. <td><code>auto indices = std::view::iota(0u, v.size());</code></td>
  583. </tr>
  584. <tr>
  585. <td>Range adaptors</td>
  586. <td><code>for (auto x : v | std::view::filter(pred)) {</code></td>
  587. </tr>
  588. </tbody>
  589. </table>
  590. <p>Below, I say a few words about each. But first I wanted to revisit an old coding challenge and recast its solution in terms of standard C++20.</p>
  591. <h1>Pythagorian Triples, Revisited</h1>
  592. <p>Some years ago now, I wrote a <a href="http://ericniebler.com/2014/04/27/range-comprehensions/">blog post</a> about how to use ranges to generate an infinite list of Pythagorean triples: 3-tuples of integers where the sum of the squares of the first two equals the square of the third.</p>
  593. <p>Below is the complete solution as it will look in standard C++20. I take the solution apart after the break.</p>
  594. <pre class="brush: cpp; notranslate">// A sample standard C++20 program that prints
  595. // the first N Pythagorean triples.
  596. #include &lt;iostream&gt;
  597. #include &lt;optional&gt;
  598. #include &lt;ranges&gt;   // New header!
  599.  
  600. using namespace std;
  601.  
  602. // maybe_view defines a view over zero or one
  603. // objects.
  604. template&lt;Semiregular T&gt;
  605. struct maybe_view : view_interface&lt;maybe_view&lt;T&gt;&gt; {
  606.  maybe_view() = default;
  607.  maybe_view(T t) : data_(std::move(t)) {
  608.  }
  609.  T const *begin() const noexcept {
  610.    return data_ ? &amp;*data_ : nullptr;
  611.  }
  612.  T const *end() const noexcept {
  613.    return data_ ? &amp;*data_ + 1 : nullptr;
  614.  }
  615. private:
  616.  optional&lt;T&gt; data_{};
  617. };
  618.  
  619. // "for_each" creates a new view by applying a
  620. // transformation to each element in an input
  621. // range, and flattening the resulting range of
  622. // ranges.
  623. // (This uses one syntax for constrained lambdas
  624. // in C++20.)
  625. inline constexpr auto for_each =
  626.  []&lt;Range R,
  627.     Iterator I = iterator_t&lt;R&gt;,
  628.     IndirectUnaryInvocable&lt;I&gt; Fun&gt;(R&amp;&amp; r, Fun fun)
  629.        requires Range&lt;indirect_result_t&lt;Fun, I&gt;&gt; {
  630.      return std::forward&lt;R&gt;(r)
  631.        | view::transform(std::move(fun))
  632.        | view::join;
  633.  };
  634.  
  635. // "yield_if" takes a bool and a value and
  636. // returns a view of zero or one elements.
  637. inline constexpr auto yield_if =
  638.  []&lt;Semiregular T&gt;(bool b, T x) {
  639.    return b ? maybe_view{std::move(x)}
  640.             : maybe_view&lt;T&gt;{};
  641.  };
  642.  
  643. int main() {
  644.  // Define an infinite range of all the
  645.  // Pythagorean triples:
  646.  using view::iota;
  647.  auto triples =
  648.    for_each(iota(1), [](int z) {
  649.      return for_each(iota(1, z+1), [=](int x) {
  650.        return for_each(iota(x, z+1), [=](int y) {
  651.          return yield_if(x*x + y*y == z*z,
  652.            make_tuple(x, y, z));
  653.        });
  654.      });
  655.    });
  656.  
  657.    // Display the first 10 triples
  658.    for(auto triple : triples | view::take(10)) {
  659.      cout &lt;&lt; '('
  660.           &lt;&lt; get&lt;0&gt;(triple) &lt;&lt; ','
  661.           &lt;&lt; get&lt;1&gt;(triple) &lt;&lt; ','
  662.           &lt;&lt; get&lt;2&gt;(triple) &lt;&lt; ')' &lt;&lt; '\n';
  663.  }
  664. }
  665. </pre>
  666. <p>The above program prints the following:</p>
  667. <pre><code>(3,4,5)
  668. (6,8,10)
  669. (5,12,13)
  670. (9,12,15)
  671. (8,15,17)
  672. (12,16,20)
  673. (7,24,25)
  674. (15,20,25)
  675. (10,24,26)
  676. (20,21,29)
  677. </code></pre>
  678. <p>This program is (lazily) generating an infinite list of Pythagorean triples, taking the first 10, and printing them out. Below is a quick rundown on how it works. Along the way, I&#8217;ll point out the parts of that solution that will be standard starting in C++20.</p>
  679. <h2><code>main()</code></h2>
  680. <p>First, let&#8217;s look at <code>main</code>, which creates the infinite list of triples and prints out the first 10. It makes repeated use of <code>for_each</code> to define the infinite list. A use like this:</p>
  681. <pre class="brush: cpp; notranslate">auto x = for_each( some-range, [](auto elem) {
  682.  return some-view;
  683. } );
  684. </pre>
  685. <p>means: For every element in <em>some-range</em>, call the lambda. Lazily collect all the views thus generated and flatten them into a new view. If the lambda were to return <code>view::single(elem)</code>, for instance &mdash; which returns a view of exactly one element &mdash; then the above is a no-op: first carve <em>some-range</em> into <em>N</em> subranges of 1-element each, then flatten them all back into a single range.</p>
  686. <p>Armed with that knowledge, we can make sense of the triply-nested invocations of <code>for_each</code>:</p>
  687. <pre class="brush: cpp; notranslate">for_each(iota(1), [](int z) {
  688.  return for_each(iota(1, z+1), [=](int x) {
  689.    return for_each(iota(x, z+1), [=](int y) {
  690. </pre>
  691. <p>This code is generating every combination of integers <code>x</code>, <code>y</code>, and <code>z</code> in some order (selecting the bounds so that <code>x</code> and <code>y</code> are never larger than <code>z</code>, because those can&#8217;t be Pythagorean triples). At each level we create structure: we start with a single range (<code>iota(1)</code>, described below), and then get a range of ranges where each inner range corresponds to all the combinations that share a value for <code>z</code>. Those inner ranges are themselves further decomposed into subranges, each of which represents all the combinations that share a value of <code>x</code>. And so on.</p>
  692. <p>The innermost lambda has <code>x</code>, <code>y</code>, and <code>z</code> and can decide whether to emit the triple or not:</p>
  693. <pre class="brush: cpp; notranslate">return yield_if(x*x + y*y == z*z,
  694.    make_tuple(x, y, z));
  695. </pre>
  696. <p><code>yield_if</code> takes a Boolean (<em>have we found a Pythagorean triple?</em>) and the triple, and either emits an empty range or a 1-element range containing the triple. That set of ranges then gets flattened, flattened, and flattened again into the infinite list of the Pythagorean triples.</p>
  697. <p>We then pipe that infinite list to <code>view::take(10)</code>, which truncates the infinite list to the first 10 elements. Then we iterate over those elements with an ordinary range-based <code>for</code> loop and print out the results. Phwew!</p>
  698. <p>Now that we have a high-level understanding of what this program is doing, we can take a closer look at the individual components.</p>
  699. <h2><code>view::iota</code></h2>
  700. <p>This is a very simple view. It takes either one or two objects of <code>Incrementable</code> type. It builds a range out of them, using the second argument as the upper bound of a half-closed (<em>i.e.,</em> exclusive) range, taking the upper bound to be an unreachable sentinel if none is specified (<em>i.e.,</em> the range is infinite). Here we use it to build a range of integers, but any incrementable types will do, including iterators.</p>
  701. <p>The name &#8220;<code>iota</code>&#8221; comes from the <code>std::iota</code> numeric algorithm, which itself has an <a href="https://stackoverflow.com/a/9244949/195873">interesting naming history</a>.</p>
  702. <h2><code>for_each</code></h2>
  703. <p>The range-v3 library comes with <code>view::for_each</code> and <code>yield_if</code>, but those haven&#8217;t been proposed yet. But <code>view::for_each</code> is a trivial composition of <code>view::transform</code> and <code>view::join</code> which <em>will</em> be part of C++20, so we can implement it as follows:</p>
  704. <pre class="brush: cpp; notranslate">inline constexpr auto for_each =
  705.  []&lt;Range R,
  706.     Iterator I = iterator_t&lt;R&gt;,
  707.     IndirectUnaryInvocable&lt;I&gt; Fun&gt;(R&amp;&amp; r, Fun fun)
  708.       requires Range&lt;indirect_result_t&lt;Fun, I&gt;&gt; {
  709.     return std::forward&lt;R&gt;(r)
  710.       | view::transform(std::move(fun))
  711.       | view::join;
  712.  };
  713. </pre>
  714. <p>This declares an object <code>for_each</code> that is a C++20 constrained generic lambda with explicitly specified template parameters. &#8220;<code>Range</code>&#8221; and &#8220;<code>IndirectUnaryInvocable</code>&#8221; are standard concepts in C++20 that live in namespace <code>std</code>. They constrain the arguments <code>r</code> and <code>fun</code> of the lambda to be a range (duh) and a function that is callable with the values of the range. We then further constrain the lambda with a trailing <code>requires</code> clause, ensuring that the function&#8217;s return type must be a <code>Range</code> as well. <code>indirect_result_t</code> will also be standard in C++20. It answers the question: if I call this function with the result of dereferencing this iterator, what type do I get back?</p>
  715. <p>The lambda first lazily transforms the range <code>r</code> by piping it to <code>view::transform</code>, moving <code>fun</code> in. <code>view::</code> is a namespace within <code>std::</code> in which all the new lazy range adaptors live. Since <code>fun</code> returns a <code>Range</code> (we required that!), the result of the transformation is a range of ranges. We then pipe that to <code>view::join</code> to flatten the ranges into one big range.</p>
  716. <p>The actual code, lines 6-8, kind of gets lost in the sea of constraints, which are not strictly necessary to use the library; I&#8217;m being a bit pedantic for didactic purposes here, so please don&#8217;t let that trip you up.</p>
  717. <p>I also could have very easily written <code>for_each</code> as a vanilla function template instead of making it an object initialized with a constrained generic lambda. I opted for an object in large part because I wanted to demonstrate how to use concepts with lambdas in C++20. Function objects have <a href="http://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/">other nice properties</a>, besides.</p>
  718. <h2><code>yield_if</code></h2>
  719. <p><code>yield_if</code> is simpler conceptually, but it requires a little legwork on our part. It is a function that takes a Boolean and an object, and it returns either an empty range (if the Boolean is false), or a range of length one containing the object. For that, we need to write our own view type, called <code>maybe_view</code>, since there isn&#8217;t one in C++20. (Not yet, at least. There is <a href="http://wg21.link/p1255">a proposal</a>.)</p>
  720. <p>Writing views is made a little simpler with the help of <code>std::view_interface</code>, which generates some of the boilerplate from <code>begin()</code> and <code>end()</code> functions that you provide. <code>view_interface</code> provides some handy members like <code>.size()</code>, <code>.operator[]</code>, <code>.front()</code>, and <code>.back()</code>.</p>
  721. <p><code>maybe_view</code> is reproduced below. Notice how it is trivially implemented in terms of <code>std::optional</code> and <code>std::view_interface</code>.</p>
  722. <pre class="brush: cpp; notranslate">template&lt;Semiregular T&gt;
  723. struct maybe_view : view_interface&lt;maybe_view&lt;T&gt;&gt; {
  724.  maybe_view() = default;
  725.  maybe_view(T t) : data_(std::move(t)) {
  726.  }
  727.  T const *begin() const noexcept {
  728.    return data_ ? &amp;*data_ : nullptr;
  729.  }
  730.  T const *end() const noexcept {
  731.    return data_ ? &amp;*data_ + 1 : nullptr;
  732.  }
  733. private:
  734.  optional&lt;T&gt; data_{};
  735. };
  736. </pre>
  737. <p>Once we have <code>maybe_view</code>, the implementation of <code>yield_if</code> is also trivial. It returns either an empty <code>maybe_view</code>, or one containing a single element, depending on the Boolean argument.</p>
  738. <pre class="brush: cpp; notranslate">inline constexpr auto yield_if =
  739.  []&lt;Semiregular T&gt;(bool b, T x) {
  740.    return b ? maybe_view{std::move(x)}
  741.             : maybe_view&lt;T&gt;{};
  742.  };
  743. </pre>
  744. <blockquote>
  745. <p><em>Note:</em> <code>maybe_view</code> owns its elements. It is generally a violation of the <code>View</code> concept&#8217;s semantic requirements for a view to own its elements because it gives the type&#8217;s copy and move operations O(<em>N</em>) behavior. However, in this case &mdash; where <em>N</em> is either 0 or 1 &mdash; we just squeak by.</p>
  746. </blockquote>
  747. <p>And that&#8217;s it. This program demonstrates how to use <code>view::iota</code>, <code>view::transform</code>, <code>view::join</code>, <code>view_interface</code>, and some standard concepts to implement a very useful bit of library functionality, and then uses it to construct an infinite list with some interesting properties. If you have used list comprehensions in Python or Haskell, this should feel pretty natural.</p>
  748. <p>But these features are just a tiny slice of the range support in C++20. Below, I go through each row of the table at the top of the post, and give an example of each.</p>
  749. <h1>Fundamental Concepts</h1>
  750. <p>The C++20 Standard Library is getting a host of generally useful concept definitions that users can use in their own code to constrain their templates and to define higher-level concepts that are meaningful for them. These all live in the new <code>&lt;concepts&gt;</code> header, and they include things like <code>Same&lt;A, B&gt;</code>, <code>ConvertibleTo&lt;From, To&gt;</code>, <code>Constructible&lt;T, Args...&gt;</code>, and <code>Regular&lt;T&gt;</code>.</p>
  751. <p>Say for instance that you have a thread pool class with an <code>enqueue</code> member function that takes something that is callable with no arguments. Today, you would write it like this:</p>
  752. <pre class="brush: cpp; notranslate">struct ThreadPool {
  753.  template &lt;class Fun&gt;
  754.  void enqueue( Fun fun );
  755. };
  756. </pre>
  757. <p>Users reading this code might wonder: what are the requirements on the type <code>Fun</code>? We can enforce the requirement in code using C++20&#8217;s <code>std::Invocable</code> concept, along with the recently-added support for abreviated function syntax:</p>
  758. <pre class="brush: cpp; notranslate">#include &lt;concepts&gt;
  759.  
  760. struct ThreadPool {
  761.  void enqueue( std::Invocable auto fun );
  762. };
  763. </pre>
  764. <p>This states that <code>fun</code> has to be invocable with no arguments. We didn&#8217;t even have to type <code>template &lt;class ...&gt;</code>! (<code>std::Invocable&lt;std::error_code &amp;&gt; auto fun</code> would declare a function that must be callable with a reference to a <code>std::error_code</code>, to take another example.)</p>
  765. <h1>Iterator and Range Concepts</h1>
  766. <p>A large part of the Standard Library concerns itself with containers, iterators, and algorithms, so it makes sense that the conceptual vocabulary would be especially rich in this area. Look for useful concept definitions like <code>Sentinel&lt;S, I&gt;</code>, <code>InputIterator&lt;I&gt;</code>, and <code>RandomAccessIterator&lt;I&gt;</code> in the <code>&lt;iterator&gt;</code> header, in addition to useful compositions like <code>IndirectRelation&lt;R, I1, I2&gt;</code> which test that <code>R</code> imposes a relation on the result of dereferencing iterators <code>I1</code> and <code>I2</code>.</p>
  767. <p>Say for example that you have a custom container type in your codebase called <code>SmallVector</code> that, like <code>std::vector</code>, can be initialized by passing it two iterators denoting a range. We can write this with concepts from <code>&lt;iterator&gt;</code> and <code>&lt;concepts&gt;</code> as follows:</p>
  768. <pre class="brush: cpp; notranslate">template &lt;std::Semiregular T&gt;
  769. struct SmallVector {
  770.  template &lt;std::InputIterator I&gt;
  771.    requires std::Same&lt;T, std::iter_value_t&lt;I&gt;&gt;
  772.  SmallVector( I i, std::Sentinel&lt;I&gt; auto s ) {
  773.    // ...push back all elements in [i,s)
  774.  }
  775.  // ...
  776. </pre>
  777. <p>Likewise, this type can get a constructor that takes a range directly using concepts defined in the new <code>&lt;ranges&gt;</code> header:</p>
  778. <pre class="brush: cpp; notranslate">  // ... as before
  779.  template &lt;std::InputRange R&gt;
  780.    requires std::Same&lt;T, std::range_value_t&lt;R&gt;&gt;
  781.  explicit SmallVector( R &amp;&amp; r )
  782.    : SmallVector(std::ranges::begin(r),
  783.                  std::ranges::end(r)) {
  784.  }
  785. };
  786. </pre>
  787. <blockquote>
  788. <p><em>Note:</em> <code>range_value_t&lt;R&gt;</code> hasn&#8217;t been formally accepted yet. It is an alias for <code>iter_value_t&lt;iterator_t&lt;R&gt;&gt;</code>.</p>
  789. </blockquote>
  790. <h1>New Convenience Iterator Traits</h1>
  791. <p>In C++17, if you want to know the value type of an iterator <code>I</code>, you have to type <code>typename std::iterator_traits&lt;I&gt;::value_type</code>. That is a mouthful. In C++20, that is vastly shortened to <code>std::iter_value_t&lt;I&gt;</code>. Here are the newer, shorter type aliases and what they mean:</p>
  792. <table>
  793. <thead>
  794. <tr>
  795. <th>New iterator type alias</th>
  796. <th>Old equivalent</th>
  797. </tr>
  798. </thead>
  799. <tbody>
  800. <tr>
  801. <td><code>iter_difference_t&lt;I&gt;</code></td>
  802. <td><code>typename iterator_traits&lt;I&gt;::difference_type</code></td>
  803. </tr>
  804. <tr>
  805. <td><code>iter_value_t&lt;I&gt;</code></td>
  806. <td><code>typename iterator_traits&lt;I&gt;::value_type</code></td>
  807. </tr>
  808. <tr>
  809. <td><code>iter_reference_t&lt;I&gt;</code></td>
  810. <td><code>typename iterator_traits&lt;I&gt;::reference</code></td>
  811. </tr>
  812. <tr>
  813. <td><code>iter_rvalue_reference&lt;I&gt;</code></td>
  814. <td><em>no equivalent, see below</em></td>
  815. </tr>
  816. </tbody>
  817. </table>
  818. <p>There is no <code>iter_category_t&lt;I&gt;</code> to get an iterator&#8217;s tag type because tag dispatching is now passé. Now that you can dispatch on iterator <em>concept</em> using language support, there is no need for tags.</p>
  819. <h1>Safe Range Access Functions</h1>
  820. <p>What is wrong with <code>std::begin</code> and <code>std::end</code>? Surprise! they are not memory safe. Consider what this code does:</p>
  821. <pre class="brush: cpp; notranslate">extern std::vector&lt;int&gt; get_data();
  822. auto it = std::begin(get_data());
  823. int i = *it; // BOOM
  824. </pre>
  825. <p><code>std::begin</code> has two overloads for <code>const</code> and non-<code>const</code> lvalues. Trouble is, rvalues bind to <code>const</code> lvalue references, leading to the dangling iterator <code>it</code> above. If we had instead called <code>std::ranges::begin</code>, the code would not have compiled.</p>
  826. <p><code>ranges::begin</code> has other niceties besides. It does the <a href="http://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/">ADL two-step</a> for you saving you from remembering to type <code>using std::begin;</code> in generic code. In other words, it dispatches to a <code>begin()</code> free function found by ADL, <em>but only if it returns an <code>Iterator</code></em>. That&#8217;s an extra bit of sanity-checking that you won&#8217;t get from <code>std::begin</code>.</p>
  827. <p>Basically, prefer <code>ranges::begin</code> in all new code in C++20 and beyond. It&#8217;s more better.</p>
  828. <h1>Prvalue and Proxy Iterator Support</h1>
  829. <p>The C++98 iterator categories are fairly restrictive. If your iterator returns a temporary (i.e., a prvalue) from its <code>operator*</code>, then the strongest iterator category it could model was <code>InputIterator</code>. <code>ForwardIterator</code> required <code>operator*</code> to return by reference. That meant that a trivial iterator that returns monotonically increasing integers by value, for example, cannot satisfy <code>ForwardIterator</code>. Shame, because that&#8217;s a useful iterator! More generally, any iterator that computes values on-demand could not model <code>ForwardIterator</code>. That&#8217;s :&#8217;-(.</p>
  830. <p>It also means that iterators that return <em>proxies</em> &mdash; types that act like references &mdash; cannot be <code>ForwardIterator</code>s. Hence, whether it was a good idea or not, <code>std::vector&lt;bool&gt;</code> is not a real container since its iterators return proxies.</p>
  831. <p>The new C++20 iterator concepts solve both of this problems with the help of <code>std::ranges::iter_swap</code> (a constrained version of <code>std::iter_swap</code>), and the new <code>std::ranges::iter_move</code>. Use <code>ranges::iter_swap(i, j)</code> to swap the values referred to by <code>i</code> and <code>j</code>. And use the following:</p>
  832. <pre class="brush: cpp; notranslate">iter_value_t&lt;I&gt; tmp = ranges::iter_move(i);
  833. </pre>
  834. <p>&#8230; to move an element at position <code>i</code> out of sequence and into the temporary object <code>tmp</code>.</p>
  835. <p>Authors of proxy iterator types can hook these two customization points to make their iterators play nicely with the constrained algorithms in the <code>std::ranges</code> namespace (see below).</p>
  836. <p>The new <code>iter_rvalue_reference_t&lt;I&gt;</code> type alias mentioned above names the return type of <code>ranges::iter_move(i)</code>.</p>
  837. <h1>Contiguous Iterator Support</h1>
  838. <p>In Stepanov&#8217;s STL, <code>RandomAccessIterator</code> is the strongest iterator category. But whether elements are <em>contiguous</em> in memory is a useful piece of information, and there exist algorithms that can take advantage of that information to become more efficient. Stepanov was aware of that but felt that raw pointers were the only interesting model of contiguous iterators, so he didn&#8217;t need to add a new category. He would have been appalled at the library vendors who ship <code>std::vector</code> implementations with wrapped debug iterators.</p>
  839. <p>TL;DR, we are now defining an extra category that subsumes (refines) <code>RandomAccessIterator</code> called <code>ContiguousIterator</code>. A type must opt-in to contiguity by defining a nested type named <code>iterator_concept</code> (note: <em>not</em> <code>iterator_category</code>) that is an alias for the new <code>std::contiguous_iterator_tag</code> tag type. Or you could specialize <code>std::iterator_traits</code> for your type and specify <code>iterator_concept</code> there.</p>
  840. <blockquote>
  841. <p>There is a whole blog post coming about <code>iterator_category</code>, <code>iterator_concept</code>, and how to write an iterator type that conforms both to the old iterator concepts and the new, with different strengths in each. It&#8217;s a brave new world of back-compat considerations.</p>
  842. </blockquote>
  843. <h1>Constrained Algorithms</h1>
  844. <p>Ever tried to pass a <code>std::list</code>&#8216;s iterator to <code>std::sort</code>? Or any other combination of nonesense? When you accidentally fail to meet an algorithm&#8217;s (unstated) type requirements today, your compiler will inform you in the most obscure and voluminous way possible, spewing errors that appear to come from within the guts of your STL implementation.</p>
  845. <p>Concepts are designed to help with this. For instance, look at this code that is using the <a href="https://github.com/CaseyCarter/cmcstl2">cmcstl2</a> reference implementation (which puts <code>std::ranges</code> in <code>std::experimental::ranges</code> for now):</p>
  846. <pre class="brush: cpp; notranslate">#include &lt;list&gt;
  847. #include &lt;stl2/algorithm.hpp&gt;
  848. using ranges = std::experimental::ranges;
  849.  
  850. int main() {
  851.  std::list&lt;int&gt; l {82,3,7,2,5,8,3,0,4,23,89};
  852.  ranges::sort( l.begin(), l.end() );
  853. }
  854. </pre>
  855. <p>Rather than an error deep in the guts of <code>ranges::sort</code>, the error message points right to the line in <code>main</code> that failed to meet the constraints of the <code>sort</code> template. &#8220;error: no matching call for <code>ranges::sort(list&lt;int&gt;::iterator, list&lt;int&gt;::iterator)</code>&#8220;, followed by a message that shows the prototype that failed to match and an explanation that the constraints within <code>RandomAccessIterator</code> we not satisfied. You can see the full error <a href="https://godbolt.org/z/6FXw65">here</a>.</p>
  856. <p>Much can be done to make the error more user-friendly, but it&#8217;s already a vast improvement over the status quo.</p>
  857. <h1>Range Algorithms</h1>
  858. <p>This one is fairly obvious. It&#8217;s been 20 years since the STL was standardized, and all I want to do is pass a <code>vector</code> to <code>sort</code>. Is that too much to ask? Nope. With C++20, you will <em>finally</em> be able to do this:</p>
  859. <pre class="brush: cpp; notranslate">std::vector&lt; int &gt; v =  // ...
  860. std::ranges::sort( v ); // Hurray!
  861. </pre>
  862. <h1>Constrained Function Objects</h1>
  863. <p>Have you ever used <code>std::less&lt;&gt;</code>, the &#8220;diamond&#8221; specializations of the comparison function objects that were added in C++14? These let you compare things without having to say up front what type you&#8217;re comparing or forcing conversions. These exist in the <code>std::ranges</code> namespace too, but you don&#8217;t have to type <code>&lt;&gt;</code> because they are not templates. Also, they have constrained function call operators. So <code>less</code>, <code>greater</code>, <code>less_equal</code>, and <code>greater_equal</code> are all constrained with <code>StrictTotallyOrderedWith</code>, for instance.</p>
  864. <p>These types are particularly handy when defining APIs that accept a user-specified relation, but default the relation to <code>operator&lt;</code> or <code>operator==</code>. For instance:</p>
  865. <pre class="brush: cpp; notranslate">template &lt;class T, Relation&lt;T, T&gt; R = ranges::less&gt;
  866. T max( T a, T b, R r = {} ) {
  867.  return r( a, b ) ? b : a;
  868. }
  869. </pre>
  870. <p>This function has the nice property that if the user specifies a relation, it will be used and the constraints guarantee that <code>R</code> is a <code>Relation</code> over type <code>T</code>. If the user <em>doesn&#8217;t</em> specify a relation, then the constraints require that <code>T</code> satisfies <code>StrictTotallyOrderedWith</code> itself. That is implicit in the fact that <code>R</code> defaults to <code>ranges::less</code>, and <code>ranges::less::operator()</code> is constrained with <code>StrictTotallyOrderedWith</code>.</p>
  871. <h1>Generalized Callables</h1>
  872. <p>In C++17, the Standard Library got a handy function: <code>std::invoke</code>. It lets you call any &#8220;Callable&#8221; thing with some arguments, where &#8220;Callable&#8221; includes ordinary function-like things in addition to pointers to members. However, the standard algorithms were not respecified to use <code>std::invoke</code>, which meant that code like the following failed to compile:</p>
  873. <pre class="brush: cpp; notranslate">struct Wizard {
  874.  void frobnicate();
  875. };
  876.  
  877. int main() {
  878.  std::vector&lt;Wizard&gt; vw { /*...*/ };
  879.  std::for_each( vw.begin(), vw.end(),
  880.                 &amp;Wizard::frobnicate ); // Nope!
  881. }
  882. </pre>
  883. <p><code>std::for_each</code> is expecting something callable like <code>fun(t)</code>, not <code>std::invoke(fun, t)</code>.</p>
  884. <p>The new algorithms in the <code>std::ranges</code> namespace are required to use <code>std::invoke</code>, so if the above code is changed to use <code>std::ranges::for_each</code>, it will work as written.</p>
  885. <h1>Projections</h1>
  886. <p>Ever wanted to sort a range of things by some property of those things? Maybe sort a vector of Employees by their ids? Or last name? Or maybe you want to seach an array of points for one where the magnitude is equal to a certain value. For those things, <em>projections</em> are very handy. A projection is a unary transformation function passed to an algorithm that gets applied to each element before the algorithm operates on the element.</p>
  887. <p>To take the example of sorting a vector of Employees by id, you can use a projection argument to <code>std::ranges::sort</code> as follows:</p>
  888. <pre class="brush: cpp; notranslate">struct Employee {
  889.  int Id;
  890.  std::string Name;
  891.  Currency Salary;
  892. };
  893.  
  894. int main() {
  895.  using namespace std;
  896.  vector&lt;Employee&gt; employees { /*...*/ };
  897.  ranges::sort( employees, ranges::less{},
  898.                &amp;Employee::Id );
  899. }
  900. </pre>
  901. <p>The third argument to <code>std::ranges::sort</code> is the projection. Notice that we used a generalized callable for it, from the previous section. This <code>sort</code> command sorts the Employees by the <code>Id</code> field.</p>
  902. <p>Or for the example of searching an array of points for one where the magnitude is equal to a certain value, you would do the following:</p>
  903. <pre class="brush: cpp; notranslate">using namespace std;
  904. array&lt; Point &gt; points { /*...*/ };
  905. auto it = ranges::find( points, value, [](auto p) {
  906.  return sqrt(p.x*p.x + p.y*p.y);
  907. } );
  908. </pre>
  909. <p>Here we are using a projection to compute a property of each element and operating on the computed property.</p>
  910. <p>Once you get the hang of projections, you&#8217;ll find they have many uses.</p>
  911. <h1>Range Utilities</h1>
  912. <p>The part of the standard library shipping in the <code>&lt;ranges&gt;</code> header has a lot of goodies. Besides an initial set of lazy range adaptors (described below), it has some handy, general-purpose utilities.</p>
  913. <h2>view_interface</h2>
  914. <p>As in the Pythagorean triples example above, your custom view types can inhert from <code>view_interface</code> to get a host of useful member functions, like <code>.front()</code>, <code>.back()</code>, <code>.empty()</code>, <code>.size()</code>, <code>.operator[]</code>, and even an explicit conversion to <code>bool</code> so that view types can be used in <code>if</code> statements:</p>
  915. <pre class="brush: cpp; notranslate">// Boolean conversion operator comes from view_interface:
  916. if ( auto evens = vec | view::filter(is_even) ) {
  917.  // yup, we have some evens. Do something.
  918. }
  919. </pre>
  920. <h2>subrange</h2>
  921. <p><code>std::ranges::subrange&lt;I, S&gt;</code> is probably the most handy of the range utilities. It is an iterator/sentinel pair that models the <code>View</code> concept. You can use it to bundle together two iterators, or an iterator and a sentinel, for when you want to return a range or call an API that expects a range.</p>
  922. <p>It also has deduction guides that make it quite painless to use. Consider the following code:</p>
  923. <pre class="brush: cpp; notranslate">auto [b,e] = subrange{vec};
  924. </pre>
  925. <p>This code is equivalent in effect to:</p>
  926. <pre class="brush: cpp; notranslate">auto b = ranges::begin(vec);
  927. auto e = ranges::end(vec);
  928. </pre>
  929. <p>The expression <code>subrange{vec}</code> deduces the iterator and sentinel template parameters from the range <code>vec</code>, and since <code>subrange</code> is tuple-like, we can unpack the iterator/sentinel pair using structured bindings.</p>
  930. <h2>ref_view</h2>
  931. <p>Although not officially merged yet, C++20 will have a <code>std::ranges::ref_view&lt;R&gt;</code> which, like <code>std::reference_wrapper</code> is, well, a wrapper around a reference. In the case of <code>ref_view</code>, it is a reference to a range. It turns an lvalue container like <code>std::vector&lt;int&gt;&amp;</code> into a <code>View</code> of the same elements that is cheap to copy: it simply wraps a pointer to the vector.</p>
  932. <h1>Range Generators</h1>
  933. <p>Now we get to the really fun stuff. The <code>&lt;ranges&gt;</code> header has a couple of ways to generate new ranges of values, including <code>std::view::iota</code> that we saw above. Here is how to use them, and what they mean:</p>
  934. <table>
  935. <thead>
  936. <tr>
  937. <th>Syntax</th>
  938. <th>Semantics</th>
  939. </tr>
  940. </thead>
  941. <tbody>
  942. <tr>
  943. <td><strong><code>view::iota(i)</code></strong></td>
  944. <td>Given the incrementable object <code>i</code>, generates an infinite range of values like <code>[i,i+1,i+2,i+3,...)</code>.</td>
  945. </tr>
  946. <tr>
  947. <td><strong><code>view::iota(i,j)</code></strong></td>
  948. <td>Given the incrementable object <code>i</code> and some other object <code>j</code> that is comparable to <code>i</code> (but not necessarily the same type), generates a range of values like <code>[i,i+1,i+2,i+3,...,j-1]</code>. Note that the upper bound (<code>j</code>) is <em>excluded</em>, which makes this form usable with iterator/sentinel pairs. It can also be used to generate the indices of a range with <code>view::iota(0u, ranges::size(rng))</code>.</td>
  949. </tr>
  950. <tr>
  951. <td><strong><code>view::single(x)</code></strong></td>
  952. <td>Construct a one-element view of the value <code>x</code>; that is, <code>[x]</code>.</td>
  953. </tr>
  954. <tr>
  955. <td><strong><code>view::empty&lt;T&gt;</code></strong></td>
  956. <td>A zero-element view of elements of type <code>T</code>.</td>
  957. </tr>
  958. <tr>
  959. <td><strong><code>view::counted(it, n)</code></strong></td>
  960. <td>Given an iterator <code>it</code> and a count <code>n</code>, constructs a finite range of <code>n</code> elements starting at the element denoted by <code>it</code>.</td>
  961. </tr>
  962. </tbody>
  963. </table>
  964. <h1>Range Adaptors</h1>
  965. <p>This is the really, <em>really</em> fun stuff. The true power of ranges lies in the ability to create pipelines that transform ranges on the fly. The range-v3 library has dozens of useful range adaptors. C++20 will only be getting a handful, but expect the set to grow over time.</p>
  966. <table>
  967. <thead>
  968. <tr>
  969. <th>Syntax</th>
  970. <th>Semantics</th>
  971. </tr>
  972. </thead>
  973. <tbody>
  974. <tr>
  975. <td><strong><code>r | view::all</code></strong></td>
  976. <td>Create a <code>View</code> over all the elements in <code>Range</code> <code>r</code>. Perhaps <code>r</code> is already a <code>View</code>. If not, turn it into one with <code>ref_view</code> if possible, or <code>subrange</code> failing that. Rvalue containers are not &#8220;viewable,&#8221; and so code like <code>std::vector&lt;int&gt;{} | view::all</code> will fail to compile.</td>
  977. </tr>
  978. <tr>
  979. <td><strong><code>r | view::filter(pred)</code></strong></td>
  980. <td>Given a viewable range <code>r</code> and a predicate <code>pred</code>, return a <code>View</code> that consists of all the elements <code>e</code> for which <code>invoke(pred, e)</code> returns <code>true</code>.</td>
  981. </tr>
  982. <tr>
  983. <td><strong><code>r | view::transform(fn)</code></strong></td>
  984. <td>Given a viewable range <code>r</code> and a function <code>fn</code>, return a <code>View</code> that consists of all the elements of <code>r</code> transformed with <code>fn</code>.</td>
  985. </tr>
  986. <tr>
  987. <td><strong><code>r | view::reverse</code></strong></td>
  988. <td>Given a viewable range <code>r</code>, return a <code>View</code> that iterates <code>r</code>&#8216;s values in reverse order.</td>
  989. </tr>
  990. <tr>
  991. <td><strong><code>r | view::take(n)</code></strong></td>
  992. <td>Given a viewable range <code>r</code>, return a <code>View</code> containing the first <code>n</code> elements of <code>r</code>, or all the elements of <code>r</code> if <code>r</code> has fewer than <code>n</code> elements.</td>
  993. </tr>
  994. <tr>
  995. <td><strong><code>r | view::join</code></strong></td>
  996. <td>Given a viewable range of ranges, flatten all the ranges into a single range.</td>
  997. </tr>
  998. <tr>
  999. <td><strong><code>r | view::split(r2)</code></strong></td>
  1000. <td>Given a viewable range <code>r</code> and a pattern range <code>r2</code>, return a <code>View</code> of <code>View</code>s where the inner ranges are delimited by <code>r2</code>. Alternativly, the delimiter can be a single value <code>v</code> which is treated as if it were <code>view::single(v)</code>.</td>
  1001. </tr>
  1002. <tr>
  1003. <td><strong><code>r | view::common</code></strong></td>
  1004. <td>Given a viewable range <code>r</code>, return a <code>View</code> for which the begin and end iterators of the range have the same type. (Some ranges use a sentinel for the end position.) This range adaptor is useful primarily as a means of interfacing with older code (like the <code>std::</code> algorithms) that expects begin and end to have the same type.</td>
  1005. </tr>
  1006. </tbody>
  1007. </table>
  1008. <p>These adaptors can be chained, so for instance, you can do the following:</p>
  1009. <pre class="brush: cpp; notranslate">using namespace std;
  1010. for ( auto &amp;&amp; e : r | view::filter(pred)
  1011.                    | view::transform(fn) ) {
  1012.  // Iterate over filtered, transformed range
  1013. }
  1014. </pre>
  1015. <p>Of course, you can also use range adaptor pipelines as arguments to the range-based algorithms in <code>std::ranges</code>:</p>
  1016. <pre class="brush: cpp; notranslate">using namespace std;
  1017. // Insert a filtered, transformed range into
  1018. // the back of container `v`.
  1019. ranges::copy( r | view::filter(pred)
  1020.                | view::transform(fn),
  1021.              back_inserter(v) );
  1022. </pre>
  1023. <p>Lazily adapting ranges is a powerful way to structure your programs. If you want a demonstration of how far this programming style can take you, see my <a href="https://www.youtube.com/watch?v=mFUXNMfaciE">CppCon keynote on ranges from 2015</a>, or just skim the code of the <a href="https://github.com/ericniebler/range-v3/blob/master/example/calendar.cpp">calendar application</a> I describe there, and note the lack of loops, branches, and overt state manipulation. &#8216;Nuf said.</p>
  1024. <h1>Future Directions</h1>
  1025. <p>Clearly, C++20 is getting a <em>lot</em> of new functionality in support of ranges. Getting here has taken a long time, mostly because nobody had ever built a fully general, industrial strength, generic library using the C++20 language support for concepts before. But now we are over that hump. All the foundational pieces are in place, and we&#8217;ve acrued a lot of knowledge in the process. Expect the feature set to expand rapidly post-C++20. There are already papers in flight.</p>
  1026. <p>Things currently in the works include:</p>
  1027. <ul>
  1028. <li>Constructors for the standard containers that accept ranges,</li>
  1029. <li>A <code>take_while</code> range adaptor that accepts a predicate and returns a view of the first <em>N</em> elements for which the predicate evaluates to <code>true</code>,</li>
  1030. <li>A <code>drop</code> range adaptor that returns a view after dropping the first <em>N</em> elements of the input range,</li>
  1031. <li>A <code>drop_while</code> view that drops elements from an input range that satisfy a predicate.</li>
  1032. <li>An <code>istream_view</code> that is parameterized on a type and that reads elements of that type from a standard <code>istream</code>,</li>
  1033. <li>A <code>zip</code> view that takes <em>N</em> ranges and produces a view where the elements are <em>N</em>-tuples of the elements of the input ranges, and</li>
  1034. <li>A <code>zip_with</code> view that takes <em>N</em> ranges and a <em>N</em>-ary function, and produces a view where the elements are the result of calling the function with the elements of the input ranges.</li>
  1035. </ul>
  1036. <p>And there&#8217;s more, lots more in range-v3 that has proven useful and will eventually be proposed by myself or some other interested range-r. Things I would especially like to see:</p>
  1037. <ul>
  1038. <li>An iterator façade class template like range-v3&#8217;s <code>basic_iterator</code>;</li>
  1039. <li>A view façade class template like range-v3&#8217;s <code>view_facade</code>;</li>
  1040. <li>Range-ified versions of the numeric algorithms (e.g., <code>accumulate</code>, <code>partial_sum</code>, <code>inner_product</code>);</li>
  1041. <li>More range generators and adaptors, like <code>view::chunk</code>, <code>view::concat</code>, <code>view::group_by</code>, <code>view::cycle</code>, <code>view::slice</code>, <code>view::stride</code>, <code>view::generate[_n]</code>, <code>view::repeat[_n]</code>, a <code>view::join</code> that takes a delimiter, <code>view::intersperse</code>, <code>view::unique</code>, and <code>view::cartesian_product</code>, to name the more important ones; and</li>
  1042. <li>A &#8220;complete&#8221; set of <em>actions</em> to go along with the views. Actions, like the adaptors in the <code>view::</code> namespace, operate on ranges and compose into pipelines, but actions act <em>eagerly</em> on whole containers, and they are potentially mutating. (The views are non-mutating.)</li>
  1043. </ul>
  1044. <p>With actions, it should be possible to do:</p>
  1045. <pre class="brush: cpp; notranslate">v = move(v) | action::sort | action::unique;
  1046. </pre>
  1047. <p>&#8230;to sort a vector and remove all duplicate elements.</p>
  1048. <p>And I haven&#8217;t even mentioned <em>asynchronous ranges</em> yet. But that&#8217;s a whole other <a href="http://ericniebler.com/2017/08/17/ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c/">blog post</a>. <img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f642.png" alt="🙂" class="wp-smiley" style="height: 1em; max-height: 1em;" /></p>
  1049. <h1>Summary</h1>
  1050. <p>C++20 is rapidly approaching, and now that the Ranges work has been officially merged into the working draft, I have been hearing from Standard Library vendors who are starting to think about implementing all of this. Only GCC is in a position to ship the ranges support any time soon, since it is the only compiler currently shipping with support for concepts. But clang has a <a href="https://github.com/saarraz/clang-concepts">concepts branch</a> which is already usable, so there is hope for concepts &#8212; and ranges &#8212; in clang trunk sometime in the not-too-distant future. And Microsoft has publicly committed to supporting <em>all</em> of C++20 including concepts and ranges, and the conformance of the Microsoft compiler has been rapidly improving, recently gaining the ability to <a href="https://blogs.msdn.microsoft.com/vcblog/2018/11/07/use-the-official-range-v3-with-msvc-2017-version-15-9/">compile range-v3</a>. So things are looking good there, too.</p>
  1051. <p>It&#8217;s a stRANGE new world. Thanks for reading.</p>
  1052. <div style="display:none">
  1053. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  1054. </div>
  1055. ]]></content:encoded>
  1056. <wfw:commentRss>https://ericniebler.com/2018/12/05/standard-ranges/feed/</wfw:commentRss>
  1057. <slash:comments>51</slash:comments>
  1058. <post-id xmlns="com-wordpress:feed-additions:1">1058</post-id> </item>
  1059. <item>
  1060. <title>Ranges, Coroutines, and React: Early Musings on the Future of Async in C++</title>
  1061. <link>https://ericniebler.com/2017/08/17/ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c</link>
  1062. <comments>https://ericniebler.com/2017/08/17/ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c/#comments</comments>
  1063. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  1064. <pubDate>Thu, 17 Aug 2017 21:41:08 +0000</pubDate>
  1065. <category><![CDATA[coroutines]]></category>
  1066. <category><![CDATA[generic-programming]]></category>
  1067. <category><![CDATA[library-design]]></category>
  1068. <category><![CDATA[ranges]]></category>
  1069. <category><![CDATA[reactive]]></category>
  1070. <category><![CDATA[std]]></category>
  1071. <category><![CDATA[std2]]></category>
  1072. <guid isPermaLink="false">http://ericniebler.com/?p=1029</guid>
  1073.  
  1074. <description><![CDATA[Disclaimer: these are my early thoughts. None of this is battle ready. You’ve been warned. Hello, Coroutines! At the recent C++ Committee meeting in Toronto, the Coroutines TS was forwarded to ISO for publication. That roughly means that the coroutine <a class="more-link" href="https://ericniebler.com/2017/08/17/ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c/">Continue reading <span class="screen-reader-text">  Ranges, Coroutines, and React: Early Musings on the Future of Async in C++</span><span class="meta-nav">&#8594;</span></a>]]></description>
  1075. <content:encoded><![CDATA[<p><em>Disclaimer: these are my early thoughts. None of this is battle ready. You’ve been warned.</em></p>
  1076. <h2>Hello, Coroutines!</h2>
  1077. <p>At the recent C++ Committee meeting in Toronto, the Coroutines TS was forwarded to ISO for publication. That roughly means that the coroutine “feature branch” is finished, and is ready to be merged into trunk (standard C++) after a suitable vetting period (no less than a year). That puts it on target for C++20. What does that mean for idiomatic modern C++?</p>
  1078. <p>Lots, actually. With the <em>resumable functions</em> (aka, stackless coroutines) from the Coroutines TS, we can do away with callbacks, event loops, and future chaining (<code>future.then()</code>) in our asynchronous APIs. Instead, our APIs can return “awaitable” types. Programmers can then just use these APIs in a synchronous-looking style, spamming <code>co_await</code> in front of any async API call and returning an awaitable type.</p>
  1079. <p>This is a bit abstract, so <a href="https://blogs.msdn.microsoft.com/vcblog/2017/02/02/using-ibuv-with-c-resumable-functions/">this blog post</a> make it more concrete. It describes how the author wrapped the interface of libuv &#8212; a C library that provides the asynchronous I/O in Node.js &#8212; in awaitables. In libuv, all async APIs take a callback and loop on an internal event loop, invoking the callback when the operation completes. Wrapping the interfaces in awaitables makes for a much better experience without the callbacks and the <a href="https://en.wikipedia.org/wiki/Inversion_of_control">inversion of control</a> they bring.</p>
  1080. <p>Below, for instance, is a function that (asynchronously) opens a file, reads from it, writes it to <code>stdout</code>, and closes it:</p>
  1081. <pre class="brush: cpp; notranslate">auto start_dump_file( const std::string&amp; str )
  1082.  -&gt; future_t&lt;void&gt;
  1083. {
  1084.  // We can use the same request object for
  1085.  // all file operations as they don't overlap.
  1086.  static_buf_t&lt;1024&gt; buffer;
  1087.  
  1088.  fs_t openreq;
  1089.  uv_file file = co_await fs_open(uv_default_loop(),
  1090.                                  &amp;openreq,
  1091.                                  str.c_str(),
  1092.                                  O_RDONLY,
  1093.                                  0);
  1094.  if (file &gt; 0)
  1095.  {
  1096.    while (1)
  1097.    {
  1098.      fs_t readreq;
  1099.      int result = co_await fs_read(uv_default_loop(),
  1100.                                    &amp;readreq,
  1101.                                    file,
  1102.                                    &amp;buffer,
  1103.                                    1,
  1104.                                    -1);
  1105.      if (result &lt;= 0)
  1106.        break;
  1107.      buffer.len = result;
  1108.      fs_t req;
  1109.      (void) co_await fs_write(uv_default_loop(),
  1110.                               &amp;req,
  1111.                               1 /*stdout*/,
  1112.                               &amp;buffer,
  1113.                               1,
  1114.                               -1);
  1115.    }
  1116.    fs_t closereq;
  1117.    (void) co_await fs_close(uv_default_loop(),
  1118.                             &amp;closereq,
  1119.                             file);
  1120.  }
  1121. }
  1122. </pre>
  1123. <p>You can see that this looks almost <em>exactly</em> like ordinary synchronous code, with two exceptions:</p>
  1124. <ol>
  1125. <li>Calls to asynchronous operations are preceded with <code>co_await</code>, and</li>
  1126. <li>The function returns an awaitable type (<code>future_t&lt;void&gt;</code>).</li>
  1127. </ol>
  1128. <p>Very nice. But this code snippet does too much in my opinion. Wouldn’t it be nice to have a reusable component for asynchronously reading a file, separate from the bit about writing it to <code>stdout</code>? What would that even look like?</p>
  1129. <h2>Hello, Ranges!</h2>
  1130. <p>Also at the recent C++ Committee meeting in Toronto, the Ranges TS was forwarded to ISO for publication. This is the first baby step toward a complete reimagining and reimplementation of the C++ standard library in which interfaces are specified in terms of <em>ranges</em> in addition to iterators.</p>
  1131. <p>Once we have &#8220;range&#8221; as an abstraction, we can build range <em>adaptors</em> and build pipelines that transform ranges of values in interesting ways. More than just a curiosity, this is a very functional style that lets you program without a lot of state manipulation. The fewer states your program can be in, the easier it is for you to reason about your code, and the fewer bugs you’ll have. (For more on that, you can see my <a href="https://www.youtube.com/watch?v=mFUXNMfaciE">2015 C++Con talk about ranges</a>; or just look at <a href="https://github.com/ericniebler/range-v3/blob/master/example/calendar.cpp">the source for a simple app</a> that prints a formatted calendar to <code>stdout</code>, and note the lack of loops, conditionals, and overt state manipulation.)</p>
  1132. <p>For instance, if we have a range of characters, we might want to lazily convert each character to lowercase. Using the <a href="https://github.com/ericniebler/range-v3/">range-v3 library</a>, you can do the following:</p>
  1133. <pre class="brush: cpp; notranslate">std::string hello("Hello, World!");
  1134. using namespace ranges;
  1135. auto lower = hello
  1136.           | view::transform([](char c){
  1137.               return (char)std::tolower(c);});
  1138. </pre>
  1139. <p>Now <code>lower</code> presents a <em>view</em> of <code>hello</code> where each character is run through the <code>tolower</code> transform on the fly.</p>
  1140. <p>Although the range adaptors haven’t been standardized yet, the Committee has already put its stamp of approval on the overall direction, including adaptors and pipelines. (See <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html">N4128</a> for the ranges position paper.) Someday, these components will all be standard, and the C++ community can encourage their use in idiomatic modern C++.</p>
  1141. <h2>Ranges + Coroutines == <em>?</em></h2>
  1142. <p>With coroutines, ranges become even more powerful. For one thing, the <code>co_yield</code> keyword makes it trivial to define your own (synchronous) ranges. Already with range-v3 you can use the following code to define a range of all the integers and apply a filter to them:</p>
  1143. <pre class="brush: cpp; notranslate">#include &lt;iostream&gt;
  1144. #include &lt;range/v3/all.hpp&gt;
  1145. #include &lt;range/v3/experimental/utility/generator.hpp&gt;
  1146.  
  1147. using namespace ranges;
  1148.  
  1149. // Define a range of all the unsigned shorts:
  1150. experimental::generator&lt;unsigned short&gt; ushorts()
  1151. {
  1152.  unsigned short u = 0;
  1153.  do { co_yield u; } while (++u);
  1154. }
  1155.  
  1156. int main()
  1157. {
  1158.  // Filter all the even unsigned shorts:
  1159.  auto evens = ushorts()
  1160.             | view::filter([](auto i) {
  1161.                   return (i % 2) == 0; });
  1162.  
  1163.  // Write the evens to cout:
  1164.  copy( evens, ostream_iterator&lt;&gt;(std::cout, "\n") );
  1165. }
  1166. </pre>
  1167. <p>Put the above code in a .cpp file, compile with a recent clang and <code>-fcoroutines-ts -std=gnu++1z</code>, and away you go. Congrats, you’re using coroutines and ranges together. This is a trivial example, but you get the idea.</p>
  1168. <h2>Asynchronous Ranges</h2>
  1169. <p>That great and all, but it’s not <em>asynchronous</em>, so who cares? If it were asynchronous, what would that look like? Moving to the first element of the range would be an awaitable operation, and then moving to every subsequent element would also be awaitable.</p>
  1170. <p>In the ranges world, moving to the first element of a range <code>R</code> is spelled “<code>auto it = begin(R)</code>”, and moving to subsequent elements is spelled “<code>++it</code>”. So for an asynchronous range, those two operations should be awaitable. In other words, given an asynchronous range <code>R</code>, we should be able to do:</p>
  1171. <pre class="brush: cpp; notranslate">// Consume a range asynchronously
  1172. for( auto it = co_await begin(R);
  1173.     it != end(R);
  1174.     co_await ++it )
  1175. {
  1176.  auto &amp;&amp; e = *it;
  1177.  do_something( e );
  1178. }
  1179. </pre>
  1180. <p>In fact, the Coroutines TS anticipates this and has a asynchronous range-based <code>for</code> loop for just this abstraction. The above code can be rewritten:</p>
  1181. <pre class="brush: cpp; notranslate">// Same as above:
  1182. for co_await ( auto&amp;&amp; e : R )
  1183. {
  1184.  do_something( e );
  1185. }
  1186. </pre>
  1187. <p>Now we have two different but closely related abstractions: <em>Range</em> and <em>AsynchronousRange</em>. In the first, <code>begin</code> returns something that models an <em>Iterator</em>. In the second, <code>begin</code> returns an <em>Awaitable</em> of an <em>AsynchronousIterator</em>. What does that buy us?</p>
  1188. <h2>Asynchronous Range Adaptors</h2>
  1189. <p>Once we have an abstraction, we can program against that abstraction. Today we have a <code>view::transform</code> that knows how to operate on synchronous ranges. It can be extended to also work with asynchronous ranges. So can all the other range adaptors: <code>filter</code>, <code>join</code>, <code>chunk</code>, <code>group_by</code>, <code>interleave</code>, <code>transpose</code>, etc, etc. So it will be possible to build a pipeline of operations, and apply the pipeline to a synchronous range to get a (lazy) synchronous transformation, and apply the <em>same exact pipeline</em> to an asynchronous range to get a non-blocking asynchronous transformation. The benefits are:</p>
  1190. <ul>
  1191. <li>The same functional style can be used for synchronous and asynchronous code, reusing the same components and the same idioms.</li>
  1192. <li>Asynchronous code, when expressed with ranges and transformations, can be made largely stateless, as can be done today with synchronous range-based code. This leads to programs with fewer states and hence fewer state-related bugs.</li>
  1193. <li>Range-based code composes very well and encourages a decomposition of problems into orthogonal pieces which are easily testable in isolation. (E.g., a <code>view::filter</code> component can be used with any input range, synchronous or asynchronous, and can be easily tested in isolation of any particular range.)</li>
  1194. </ul>
  1195. <p>Another way to look at this is that synchronous ranges are an example of a <em>pull-based</em> interface: the user extracts elements from the range and processes them one at a time. Asynchronous ranges, on the other hand, represent more of a <em>push-based</em> model: things happen when data shows up, whenever that may be. This is akin to the <em>reactive</em> style of programming.</p>
  1196. <p><strong>By using ranges and coroutines together, we unify push and pull based idioms into a consistent, functional style of programming.</strong> And that’s going to be important, I think.</p>
  1197. <h2>Back to LibUV</h2>
  1198. <p>Earlier, we wondered about a reusable libuv component that used its asynchronous operations to read a file. Now we know what such a component could look like: an asynchronous range. Let’s start with an asynchronous range of characters. (Here I’m glossing over the fact that libuv deals with UTF-8, not ASCII. I’m also ignoring errors, which is another can of worms.)</p>
  1199. <pre class="brush: cpp; notranslate">auto async_file( const std::string&amp; str )
  1200.  -&gt; async_generator&lt;char&gt;
  1201. {
  1202.  // We can use the same request object for
  1203.  // all file operations as they don't overlap.
  1204.  static_buf_t&lt;1024&gt; buffer;
  1205.  
  1206.  fs_t openreq;
  1207.  uv_file file = co_await fs_open(uv_default_loop(),
  1208.                                  &amp;openreq,
  1209.                                  str.c_str(),
  1210.                                  O_RDONLY,
  1211.                                  0);
  1212.  if (file &gt; 0)
  1213.  {
  1214.    while (1)
  1215.    {
  1216.      fs_t readreq;
  1217.      int result = co_await fs_read(uv_default_loop(),
  1218.                                    &amp;readreq,
  1219.                                    file,
  1220.                                    &amp;buffer,
  1221.                                    1,
  1222.                                    -1);
  1223.      if (result &lt;= 0)
  1224.        break;
  1225.      // Yield the characters one at a time.
  1226.      for ( int i = 0; i &lt; result; ++i )
  1227.      {
  1228.        co_yield buffer.buffer[i];
  1229.      }
  1230.    }
  1231.    fs_t closereq;
  1232.    (void) co_await fs_close(uv_default_loop(),
  1233.                             &amp;closereq,
  1234.                             file);
  1235.  }
  1236. }
  1237. </pre>
  1238. <p>The <code>async_file</code> function above asynchronously reads a block of text from the file and then <code>co_yield</code>s the individual characters one at a time. The result is an asynchronous range of characters: <code>async_generator&lt;char&gt;</code>. (For an implementation of <code>async_generator</code>, look in <a href="https://github.com/lewissbaker/cppcoro">Lewis Baker’s cppcoro library</a>.)</p>
  1239. <p>Now that we have an asynchronous range of characters representing the file, we can apply transformations to it. For instance, we could convert all the characters to lowercase:</p>
  1240. <pre class="brush: cpp; notranslate">// Create an asynchronous range of characters read
  1241. // from a file and lower-cased:
  1242. auto async_lower = async_file("some_input.txt")
  1243.                 | view::transform([](char c){
  1244.                     return (char)std::tolower(c);});
  1245. </pre>
  1246. <p>That’s the same transformation we applied above to a <code>std::string</code> synchronously, but here it&#8217;s used asynchronously. Such an asynchronous range can then be passed through further transforms, asynchronously written out, or passed to an asynchronous <code>std::</code> algorithm (because we’ll need those, too!)</p>
  1247. <h2>One More Thing</h2>
  1248. <p>I hear you saying, “Processing a file one character at a time like this would be too slow! I want to operate on chunks.” The above <code>async_file</code> function is <em>still</em> doing too much. It should be an asynchronous range of chunks. Let’s try again:</p>
  1249. <pre class="brush: cpp; notranslate">auto async_file_chunk( const std::string&amp; str )
  1250.  -&gt; async_generator&lt;static_buf_t&lt;1024&gt;&amp;&gt;
  1251. {
  1252.  // We can use the same request object for
  1253.  // all file operations as they don't overlap.
  1254.  static_buf_t&lt;1024&gt; buffer;
  1255.  
  1256.  fs_t openreq;
  1257.  uv_file file = co_await fs_open(uv_default_loop(),
  1258.                                  &amp;openreq,
  1259.                                  str.c_str(),
  1260.                                  O_RDONLY,
  1261.                                  0);
  1262.  if (file &gt; 0)
  1263.  {
  1264.    while (1)
  1265.    {
  1266.      fs_t readreq;
  1267.      int result = co_await fs_read(uv_default_loop(),
  1268.                                    &amp;readreq,
  1269.                                    file,
  1270.                                    &amp;buffer,
  1271.                                    1,
  1272.                                    -1);
  1273.      if (result &lt;= 0)
  1274.        break;
  1275.      // Just yield the buffer.
  1276.      buffer.len = result;
  1277.      co_yield buffer;
  1278.    }
  1279.    fs_t closereq;
  1280.    (void) co_await fs_close(uv_default_loop(),
  1281.                             &amp;closereq,
  1282.                             file);
  1283.  }
  1284. }
  1285. </pre>
  1286. <p>Now if I want to, I can asynchronously read a block and asynchronously write the block, as the original code was doing, but while keeping those components separate, as they should be.</p>
  1287. <p>For some uses, a flattened view would be more convenient. No problem. That’s what the adaptors are for. If <code>static_buf_t</code> is a (synchronous) range of characters, we already have the tools we need:</p>
  1288. <pre class="brush: cpp; notranslate">// Create an asynchronous range of characters read from a
  1289. // chunked file and lower-cased:
  1290. auto async_lower = async_file_chunk("some_input.txt")
  1291.                 | view::join
  1292.                 | view::transform([](char c){
  1293.                     return (char)std::tolower(c);});
  1294. </pre>
  1295. <p>Notice the addition of <code>view::join</code>. Its job is to take a range of ranges and flatten it. Let’s see what joining an asynchronous range might look like:</p>
  1296. <pre class="brush: cpp; notranslate">template &lt;class AsyncRange&gt;
  1297. auto async_join( AsyncRange&amp;&amp; rng )
  1298.  -&gt; async_generator&lt;range_value_t&lt;
  1299.       async_range_value_t&lt;AsyncRange&gt;&gt;&gt;
  1300. {
  1301.  for co_await ( auto&amp;&amp; chunk : rng )
  1302.  {
  1303.    for ( auto&amp;&amp; e : chunk )
  1304.      co_yield e;
  1305.  }
  1306. }
  1307. </pre>
  1308. <p>We (asynchronously) loop over the outer range, then (synchronously) loop over the inner ranges, and <code>co_yield</code> each value. Pretty easy. From there, it’s just a matter of rigging up <code>operator|</code> to <code>async_join</code> to make joining work in pipelines. (A fully generic <code>view::join</code> will be more complicated than that since both the inner and outer ranges can be either synchronous or asynchronous, but this suffices for now.)</p>
  1309. <h2>Summary</h2>
  1310. <p>With ranges and coroutines together, we can unify the push and pull programming idioms, bringing ordinary C++ and reactive C++ closer together. The C++ Standard Library is already evolving in this direction, and I&#8217;m working to make that happen both on the Committee and internally at Facebook.</p>
  1311. <p>There’s LOTS of open questions. How well does this perform at runtime? Does this scale? Is it flexible enough to handle lots of interesting use cases? How do we handle errors in the middle of an asynchronous pipeline? What about splits and joins in the async call graph? Can this handle streaming interfaces? And so on. I’ll be looking into all this, but at least for now I have a promising direction, and that’s fun.</p>
  1312. <div style="display:none">
  1313. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  1314. </div>
  1315. ]]></content:encoded>
  1316. <wfw:commentRss>https://ericniebler.com/2017/08/17/ranges-coroutines-and-react-early-musings-on-the-future-of-async-in-c/feed/</wfw:commentRss>
  1317. <slash:comments>20</slash:comments>
  1318. <post-id xmlns="com-wordpress:feed-additions:1">1029</post-id> </item>
  1319. <item>
  1320. <title>Post-Conditions on Self-Move</title>
  1321. <link>https://ericniebler.com/2017/03/31/post-conditions-on-self-move/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=post-conditions-on-self-move</link>
  1322. <comments>https://ericniebler.com/2017/03/31/post-conditions-on-self-move/#comments</comments>
  1323. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  1324. <pubDate>Fri, 31 Mar 2017 15:50:21 +0000</pubDate>
  1325. <category><![CDATA[c++11]]></category>
  1326. <category><![CDATA[library-design]]></category>
  1327. <guid isPermaLink="false">http://ericniebler.com/?p=992</guid>
  1328.  
  1329. <description><![CDATA[UPDATE April 8, 2016 This post has been edited since publication to reflect my evolving understanding. As a result of the issues raised in this post, it&#8217;s possible that the committee decides to strengthen the post-conditions on move, so the <a class="more-link" href="https://ericniebler.com/2017/03/31/post-conditions-on-self-move/">Continue reading <span class="screen-reader-text">  Post-Conditions on Self-Move</span><span class="meta-nav">&#8594;</span></a>]]></description>
  1330. <content:encoded><![CDATA[<p><strong>UPDATE April 8, 2016</strong> This post has been edited since publication to reflect my evolving understanding. As a result of the issues raised in this post, it&#8217;s possible that the committee decides to strengthen the post-conditions on move, so the recommendations made here may evolve further. Stay tuned.</p>
  1331. <p><em>TL;DR:</em> In addition to the usual rule about <strong>move operations leaving the source object in a valid but unspecified state</strong>, we can add an additional rule:</p>
  1332. <p><strong><em>Self</em>-move assignment should “work” and <em>at the very least</em> leave the object in a valid but unspecified state.</strong></p>
  1333. <h2>Discussion</h2>
  1334. <p>What do you think the following code should do?</p>
  1335. <pre class="brush: cpp; notranslate">X x = {/*something*/};
  1336. x = std::move(x);
  1337. </pre>
  1338. <p>Yes, it’s dumb, but with our alias-happy language, it can happen. So what does the standard say about this? For that we turn to [res.on.arguments]/p1.3 taken from the library introduction (emphasis mine):</p>
  1339. <blockquote>
  1340. <p>If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. [&#8230;] If a program casts an lvalue to an xvalue while passing that lvalue to a library function (e.g. by calling the function with the argument <code>std::move(x)</code>), the program is effectively asking that function to treat that lvalue as a temporary. <strong>The implementation is free to optimize away aliasing checks which might be needed if the argument <strike>was</strike><u>were</u> an lvalue.</strong></p>
  1341. </blockquote>
  1342. <p>(I fixed the grammar mistake because I am a Huge Dork.) The above <em>seems</em> to say that <code>std::swap(x, x)</code> is playing with fire, because <code>std::swap</code> is implemented as follows:</p>
  1343. <pre class="brush: cpp; notranslate">template &lt;class T&gt;
  1344. void swap(T&amp; a, T&amp; b) {
  1345.  auto x(std::move(a));
  1346.  a = std::move(b); // Here be dragons
  1347.  b = std::move(x);
  1348. }
  1349. </pre>
  1350. <p>If <code>a</code> and <code>b</code> refer to the same object, the second line of <code>std::swap</code> does a self-move assign. Blamo! Undefined behavior, right?</p>
  1351. <p>Such was what I thought when I first wrote this post until Howard Hinnant drew my attention to the requirements table for the MoveAssignable concept, which says that for the expression <code>t = rv</code> (emphasis mine):</p>
  1352. <blockquote>
  1353. <p><strong>If <code>t</code> and <code>rv</code> do not refer to the same object</strong>, <code>t</code> is equivalent to the value of <code>rv</code> before the assignment [&#8230;] <code>rv</code>’s state is unspecified. [ Note: rv must still meet the requirements of the library component that is using it, whether or not <code>t</code> and <code>rv</code> refer to the same object. [&#8230;] &#8211;end note]</p>
  1354. </blockquote>
  1355. <p>Ah, ha! So here we have it. After a self-move, the object is required to be in a valid-but-unspecified state.</p>
  1356. <p>My attention we drawn to this issue during a code review of a change I wanted to make to <a href="https://github.com/facebook/folly">Folly</a>&#8216;s <a href="https://github.com/facebook/folly/blob/master/folly/docs/Function.md"><code>Function</code></a> class template. I wanted to change this:</p>
  1357. <pre class="brush: cpp; notranslate">Function&amp; operator=(Function&amp;&amp; that) noexcept {
  1358.  if (this != &amp;that) {
  1359.    // do the move
  1360.  }
  1361.  return *this;
  1362. }
  1363. </pre>
  1364. <p>to this:</p>
  1365. <pre class="brush: cpp; notranslate">Function&amp; operator=(Function&amp;&amp; that) noexcept {
  1366.  assert(this != &amp;that);
  1367.  // do the move
  1368.  return *this;
  1369. }
  1370. </pre>
  1371. <p>The reason: let’s make moves as fast as possible and take advantage of the fact that Self-Moves Shouldn’t Happen. We assert, fix up the places that get it wrong, and make our programs an iota faster. Right?</p>
  1372. <p>Not so fast, said one clued-in reviewer. Self-swaps can happen quite easily in generic algorithms, and they shouldn’t trash the state of the object or the state of the program. This rang true, and so begin my investigation.</p>
  1373. <p>A few Google searches later turned up <a href="https://stackoverflow.com/questions/9322174/move-assignment-operator-and-if-this-rhs/9322542#9322542">this StackOverflow gem from Howard Hinnant</a>. C++ wonks know Howard Hinnant. He’s the author of libc++, and an old time C++ library developer. (Remember <a href="https://en.wikipedia.org/wiki/CodeWarrior">Metrowerks CodeWarrior</a>? No? Get off my lawn.) He also happens to be the person who wrote the proposal to add rvalue references to the language, so you know, Howard’s given this some thought. First Howard says this:</p>
  1374. <blockquote>
  1375. <p>Some will argue that <code>swap(x, x)</code> is a good idea, or just a necessary evil. And this, if the swap goes to the default swap, can cause a self-move-assignment.</p>
  1376. <p>I disagree that <code>swap(x, x)</code> is <strong>ever</strong> a good idea. If found in my own code, I will consider it a performance bug and fix it.</p>
  1377. </blockquote>
  1378. <p>But then in an <strong>Update</strong>, he backtracks:</p>
  1379. <blockquote>
  1380. <p>I&#8217;ve given this issue some more thought, and changed my position somewhat. I now believe that assignment should be tolerant of self assignment, but that the post conditions on copy assignment and move assignment are different:</p>
  1381. <p>For copy assignment:</p>
  1382. <pre class="brush: cpp; notranslate">x = y;
  1383. </pre>
  1384. <p>one should have a post-condition that the value of <code>y</code> should not be altered. When <code>&amp;x == &amp;y</code> then this postcondition translates into: self copy assignment should have no impact on the value of <code>x</code>.</p>
  1385. <p>For move assignment:</p>
  1386. <pre class="brush: cpp; notranslate">x = std::move(y);
  1387. </pre>
  1388. <p>one should have a post-condition that <code>y</code> has a valid but unspecified state. When <code>&amp;x == &amp;y</code> then this postcondition translates into: <code>x</code> has a valid but unspecified state. I.e. self move assignment does not have to be a no-op. But it should not crash. This post-condition is consistent with allowing <code>swap(x, x)</code> to just work [&#8230;]</p>
  1389. </blockquote>
  1390. <p>When Howard Hinnant changes his mind about something having to do with library design, I sit up and take note, because it means that something very deep and subtle is going on. In this case, it means I’ve been writing bad move assignment operators for years.</p>
  1391. <p>By Howard’s yardstick &#8212; and by the requirements for the MoveAssignable concept in the standard, thanks Howard! &#8212; this move assignment operator is wrong:</p>
  1392. <pre class="brush: cpp; notranslate">Function&amp; operator=(Function&amp;&amp; that) noexcept {
  1393.  assert(this != &amp;that); // No! Bad C++ programmer!
  1394.  // do the move
  1395.  return *this;
  1396. }
  1397. </pre>
  1398. <p>Move assignment operators <em>should</em> accept self-moves and do no evil; indeed for <code>std::swap(f, f)</code> to work it <em>must</em>.</p>
  1399. <p>That’s not the same as saying it needs to preserve the object’s value, though, and not preserving the object’s value can be a performance win. It can save a branch, for instance. Here is how I reformulated <code>folly::Function</code>’s move assignment operator[*]:</p>
  1400. <pre class="brush: cpp; notranslate">Function&amp; operator=(Function&amp;&amp; that) noexcept {
  1401.  clear_();        // Free all of the resources owned by *this
  1402.  moveFrom_(that); // Move that's guts into *this.
  1403.  return *this;
  1404. }
  1405. </pre>
  1406. <p>[*] Well, not exactly, but that’s the gist.</p>
  1407. <p>Of note is that <code>clear_()</code> leaves <code>*this</code> in a state such that it is still OK to <code>moveFrom_(*this)</code>, which is what happens when <code>that</code> and <code>*this</code> are the same object. In the case of <code>Function</code>, it just so happens that the effect of this code is to put the <code>Function</code> object back into the default-constructed state, obliterating the previous value. The particular final state of the object isn’t important though, so long as it is still valid.</p>
  1408. <h2>Summary</h2>
  1409. <p>So, as always we have the rule about moves:</p>
  1410. <p><strong>Move operations should leave the source object in a valid but unspecified state.</strong></p>
  1411. <p>And to that we can add an additional rule:</p>
  1412. <p><strong>Self-moves should do no evil and leave the object in a valid but unspecified state.</strong></p>
  1413. <p>If you want to go further and leave the object unmodified, that&#8217;s not wrong <em>per se</em>, but it’s not required by the standard as it is today. Changing the value is perfectly OK (Howard and the standard say so!), and doing that might save you some cycles.</p>
  1414. <p>TIL</p>
  1415. <div style="display:none">
  1416. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  1417. </div>
  1418. ]]></content:encoded>
  1419. <wfw:commentRss>https://ericniebler.com/2017/03/31/post-conditions-on-self-move/feed/</wfw:commentRss>
  1420. <slash:comments>22</slash:comments>
  1421. <post-id xmlns="com-wordpress:feed-additions:1">992</post-id> </item>
  1422. <item>
  1423. <title>Iterators++, Part 3</title>
  1424. <link>https://ericniebler.com/2015/03/03/iterators-plus-plus-part-3/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=iterators-plus-plus-part-3</link>
  1425. <comments>https://ericniebler.com/2015/03/03/iterators-plus-plus-part-3/#comments</comments>
  1426. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  1427. <pubDate>Wed, 04 Mar 2015 02:32:56 +0000</pubDate>
  1428. <category><![CDATA[generic-programming]]></category>
  1429. <category><![CDATA[library-design]]></category>
  1430. <category><![CDATA[ranges]]></category>
  1431. <category><![CDATA[std]]></category>
  1432. <guid isPermaLink="false">http://ericniebler.com/?p=918</guid>
  1433.  
  1434. <description><![CDATA[This is the fourth and final post in a series about proxy iterators, the limitations of the existing STL iterator concept hierarchy, and what could be done about it. The first three posts describe the problems of proxy iterators, the <a class="more-link" href="https://ericniebler.com/2015/03/03/iterators-plus-plus-part-3/">Continue reading <span class="screen-reader-text">  Iterators++, Part 3</span><span class="meta-nav">&#8594;</span></a>]]></description>
  1435. <content:encoded><![CDATA[<p>This is the fourth and final post in a series about <strong>proxy iterators</strong>, the limitations of the existing STL iterator concept hierarchy, and what could be done about it. The <a href="http://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/">first</a> <a href="http://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/">three</a> <a href="http://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/">posts</a> describe the problems of proxy iterators, the way to swap and move their elements, and how to rigorously define what an Iterator is.</p>
  1436. <p>This time around I&#8217;ll be focusing on the final problem: how to properly constrain the higher-order algorithms so that they work with proxy iterators.</p>
  1437. <h2>A Unique Algorithm</h2>
  1438. <p>In this post, I&#8217;ll be looking at one algorithm in particular and how it interacts with proxy iterators: <code>unique_copy</code>. Here is its prototype:</p>
  1439. <pre class="brush: cpp; notranslate">template &lt;class InIter, class OutIter, class Fn&gt;
  1440. OutIter unique_copy(InIter first, InIter last,
  1441.                    OutIter result, Fn binary_pred);
  1442. </pre>
  1443. <p>This algorithm copies elements from one range to another, skipping adjacent elements that are equal, using a predicate for the comparison.</p>
  1444. <p>Consider the following invocation:</p>
  1445. <pre class="brush: cpp; notranslate">std::stringstream sin{"1 1 2 3 3 3 4 5"};
  1446. unique_copy(
  1447.  std::istream_iterator&lt;int&gt;{sin},
  1448.  std::istream_iterator&lt;int&gt;{},
  1449.  std::ostream_iterator&lt;int&gt;{std::cout, " "},
  1450.  std::equal_to&lt;int&gt;{} );
  1451. </pre>
  1452. <p>This reads a bunch of ints from <code>sin</code> and writes the unique ones to <code>cout</code>. Simple, right? This code prints:</p>
  1453. <pre><code>1 2 3 4 5
  1454. </code></pre>
  1455. <p>Think for a minute how you would implement <code>unique_copy</code>. First you read an int from the stream. Then you write it out to the other stream. Then you read another int. You want to compare it to the last one. Ah! You need to <em>save</em> the last element locally so that you can do the comparisons. Interesting.</p>
  1456. <p>When I really want to understand how some part of the STL works, I check out how the feature is implemented in ye olde <a href="https://www.sgi.com/tech/stl/">SGI STL</a>. This codebase is so old, it may have first been written on parchment and compiled by monks. But it&#8217;s the cleanest and most straightforward STL implementation I know, and I recommend reading it through. Here, modulo some edits for readability, is the relevant part of <code>unique_copy</code>:</p>
  1457. <pre class="brush: cpp; notranslate">// Copyright (c) 1994
  1458. // Hewlett-Packard Company
  1459. // Copyright (c) 1996
  1460. // Silicon Graphics Computer Systems, Inc.
  1461. template &lt;class InIter, class OutIter, class Fn,
  1462.          class _Tp&gt;
  1463. OutIter
  1464. __unique_copy(InIter first, InIter last,
  1465.              OutIter result,
  1466.              Fn binary_pred, _Tp*) {
  1467.  _Tp value = *first;
  1468.  *result = value;
  1469.  while (++first != last)
  1470.    if (!binary_pred(value, *first)) {
  1471.      value = *first;
  1472.      *++result = value;
  1473.    }
  1474.  return ++result;
  1475. }
  1476. </pre>
  1477. <p>(The calling code ensures that <code>first != last</code>, which explains why this code skips that check. And the strange <code>_Tp*</code> argument is so that the iterator&#8217;s value type can be deduced; the monks couldn&#8217;t compile traits classes.) Note the <code>value</code> local variable on line 11, and especially note line 14, where it passes a <em>value</em> and a <em>reference</em> to <code>binary_pred</code>. Keep that in mind because it&#8217;s important!</p>
  1478. <h2>The Plot Thickens</h2>
  1479. <p>You probably know more about <code>unique_copy</code> now than you ever cared to. Why do I bring it up? Because it&#8217;s <em>super problematic</em> when used with proxy iterators. Think about what happens when you try to pass <code>vector&lt;bool&gt;::iterator</code> to the above <code>__unique_copy</code> function:</p>
  1480. <pre class="brush: cpp; notranslate">std::vector&lt;bool&gt; vb{true, true, false, false};
  1481. using R = std::vector&lt;bool&gt;::reference;
  1482. __unique_copy(
  1483.  vb.begin(), vb.end(),
  1484.  std::ostream_iterator&lt;bool&gt;{std::cout, " "},
  1485.  [](R b1, R b2) { return b1 == b2; }, (bool*)0 );
  1486. </pre>
  1487. <p>This <em>should</em> write a &#8220;true&#8221; and a &#8220;false&#8221; to <code>cout</code>, but it doesn&#8217;t compile. Why? The lambda is expecting to be passed two objects of <code>vector&lt;bool&gt;</code>&#8216;s proxy reference type, but remember how <code>__unique_copy</code> calls the predicate:</p>
  1488. <pre class="brush: cpp; notranslate">if (!binary_pred(value, *first)) { /*...*/
  1489. </pre>
  1490. <p>That&#8217;s a <code>bool&amp;</code> and a <code>vector&lt;bool&gt;::reference</code>. Ouch!</p>
  1491. <p>They&#8217;re just bools, and bools are cheap to copy, so take them by value. Problem solved. Well, sure, but what if they weren&#8217;t bools? What if we proxied a sequence of things that are expensive to copy? Now the problem is harder.</p>
  1492. <p>So for lack of anything better (and pretending that bools are expensive to copy, bear with me), you write the lambda like this:</p>
  1493. <pre class="brush: cpp; notranslate">[](bool&amp; b1, R b2) { return b1 == b2; }
  1494. </pre>
  1495. <p>Yuk. Now you port this code to another STL that happens to call the predicate with reversed arguments and the code breaks again. <img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f641.png" alt="🙁" class="wp-smiley" style="height: 1em; max-height: 1em;" /></p>
  1496. <p>My point is this: once we introduce proxy iterators into the mix, it becomes non-obvious how to define predicates for use with the algorithms. Sometimes the algorithms call the predicates with references, sometimes with values, and sometimes &#8212; like <code>unique_copy</code> &#8212; with a mix of both. Algorithms like <code>sort</code> first call the predicate one way, and then later call it another way. <em>Vive la différence!</em></p>
  1497. <h2>A Common Fix</h2>
  1498. <p>This problem has a very simple solution in C++14: a generic lambda. We can write the above code simply, portably, and optimally as follows:</p>
  1499. <pre class="brush: cpp; notranslate">std::vector&lt;bool&gt; vb{true, true, false, false};
  1500. std::unique_copy(
  1501.  vb.begin(), vb.end(),
  1502.  std::ostream_iterator&lt;bool&gt;{std::cout, " "},
  1503.  [](auto&amp;&amp; b1, auto&amp;&amp; b2) { return b1 == b2; } );
  1504. </pre>
  1505. <p>No matter what <code>unique_copy</code> throws at this predicate, it will accommodate it with grace and style.</p>
  1506. <p>But still. Polymorphic function objects feel like a big hammer. Some designs require monomorphic functions, like <code>std::function</code> or virtuals, or maybe even a function pointer if you have to interface with C. My point is, it feels wrong for the STL to <em>require</em> the use of a polymorphic function for correctness.</p>
  1507. <p>To restate the problem, we don&#8217;t know how to write a monomorphic predicate for <code>unique_copy</code> when our sequence is proxied because <code>value_type&amp;</code> may not convert to <code>reference</code>, and <code>reference</code> may not convert to <code>value_type&amp;</code>. If only there were some other type, some other <em>reference-like</em> type, they could both convert to&#8230;</p>
  1508. <p>But there is! If you read my <a href="http://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/">last post</a>, you know about <code>common_reference</code>, a trait that computes a reference-like type (possibly a proxy) to which two other references can bind (or convert). In order for a proxy iterator to model the Iterator concept, I required that an iterator&#8217;s <code>reference</code> type and its <code>value_type&amp;</code> must share a common reference. At the time, I insinuated that the only use for such a type is to satisfy the concept-checking machinery. But there&#8217;s another use for it: the common reference is the type we could use to define our monomorphic predicate.</p>
  1509. <p>I can imagine a future STL providing the following trait:</p>
  1510. <pre class="brush: cpp; notranslate">// An iterator's common reference type:
  1511. template &lt;InputIterator I&gt;
  1512. using iterator_common_reference_t =
  1513.  common_reference_t&lt;
  1514.    typename iterator_traits&lt;I&gt;::value_type &amp;
  1515.    typename iterator_traits&lt;I&gt;::reference&gt;;
  1516. </pre>
  1517. <p>We could use that trait to write the predicate as follows:</p>
  1518. <pre class="brush: cpp; notranslate">using I = vector&lt;bool&gt;::iterator;
  1519. using C = iterator_common_reference_t&lt;I&gt;;
  1520. auto binary_pred = [](C r1, C r2) {
  1521.  return r1 == r2;
  1522. };
  1523. </pre>
  1524. <p>That&#8217;s certainly a fair bit of hoop-jumping just to define a predicate. But it&#8217;s not some new complexity that I&#8217;m introducing. <code>unique_copy</code> and <code>vector&lt;bool&gt;</code> have been there since 1998. I&#8217;m just trying to make them play nice.</p>
  1525. <p>And these hoops almost never need to be jumped. You&#8217;ll only need to use the common reference type when all of the following are true: (a) you are dealing with a proxied sequence (or are writing generic code that could deal with proxied sequences), (b) taking the arguments by value is undesirable, and (c) using a polymorphic function is impossible or impractical for some reason. I wouldn&#8217;t think that&#8217;s very often.</p>
  1526. <h2>Algorithm Constraints</h2>
  1527. <p>So that&#8217;s how things look from the perspective of the end user. How do they look from the other side, from the perspective of the algorithm author? In particular, how should <code>unique_copy</code> look once we use Concepts Lite to constrain the algorithm?</p>
  1528. <p>The <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf">Palo Alto TR</a> takes a stab at it. Here is how it constrains <code>unique_copy</code>:</p>
  1529. <pre class="brush: cpp; notranslate">template &lt;InputIterator I, WeaklyIncrementable Out,
  1530.          Semiregular R&gt;
  1531. requires Relation&lt;R, ValueType&lt;I&gt;, ValueType&lt;I&gt;&gt; &amp;&amp;
  1532.         IndirectlyCopyable&lt;I, Out&gt;
  1533. Out unique_copy(I first, I last, Out result, R comp);
  1534. </pre>
  1535. <p>There&#8217;s a lot going on there, but the relevant part is <code>Relation&lt;R, ValueType&lt;I&gt;, ValueType&lt;I&gt;&gt;</code>. In other words, the type <code>R</code> must be an equivalence relation that accepts arguments of the range&#8217;s <em>value type</em>. For all the reasons we&#8217;ve discussed, that doesn&#8217;t work when dealing with a proxied range like <code>vector&lt;bool&gt;</code>.</p>
  1536. <p>So what should the constraint be? Maybe it should be <code>Relation&lt;R, ValueType&lt;I&gt;, Reference&lt;I&gt;&gt;</code>? But no, <code>unique_copy</code> doesn&#8217;t <em>always</em> need to copy a value into a local. Only when neither the input nor the output iterators model ForwardIterator. So sometimes the <code>unique_copy</code> calls the predicate like <code>pred(*i,*j)</code> and sometimes like <code>pred(value, *i)</code>. The constraint has to be general enough to accommodate that.</p>
  1537. <p>Maybe it could also use the iterator&#8217;s common reference type? What if we constrained <code>unique_copy</code> like this:</p>
  1538. <pre class="brush: cpp; notranslate">template &lt;InputIterator I, WeaklyIncrementable Out,
  1539.          Semiregular R&gt;
  1540. requires Relation&lt;R, CommonReferenceType&lt;I&gt;,
  1541.                     CommonReferenceType&lt;I&gt;&gt; &amp;&amp;
  1542.         IndirectlyCopyable&lt;I, Out&gt;
  1543. Out unique_copy(I first, I last, Out result, R comp);
  1544. </pre>
  1545. <p>This constraint make a promise to callers: &#8220;I will only pass objects of type <code>CommonReferenceType&lt;I&gt;</code> to the predicate.&#8221; But that&#8217;s a lie. It&#8217;s not how <code>unique_copy</code> is actually implemented. We could change the implementation to fulfill this promise by casting the arguments before passing them to the predicate, but that&#8217;s ugly and potentially inefficient.</p>
  1546. <p>Really, I think we have to check that the predicate is callable with all the possible combinations of values and references. That sucks, but I don&#8217;t see a better option. With some pruning, these are the checks that I think matter enough to be required:</p>
  1547. <pre class="brush: cpp; notranslate">Relation&lt;R, ValueType&lt;I&gt;, ValueType&lt;I&gt;&gt; &amp;&amp;
  1548. Relation&lt;R, ValueType&lt;I&gt;, ReferenceType&lt;I&gt;&gt; &amp;&amp;
  1549. Relation&lt;R, ReferenceType&lt;I&gt;, ValueType&lt;I&gt;&gt; &amp;&amp;
  1550. Relation&lt;R, ReferenceType&lt;I&gt;, ReferenceType&lt;I&gt;&gt; &amp;&amp;
  1551. Relation&lt;R, CommonReferenceType&lt;I&gt;, CommonReferenceType&lt;I&gt;&gt;
  1552. </pre>
  1553. <p>As an implementer, I don&#8217;t want to write all that, and our users don&#8217;t want to read it, so we can bundle it up nice and neat:</p>
  1554. <pre class="brush: cpp; notranslate">IndirectRelation&lt;R, I, I&gt;
  1555. </pre>
  1556. <p>That&#8217;s easier on the eyes and on the brain.</p>
  1557. <h2>Interesting Indirect Invokable Implications</h2>
  1558. <p>In short, I think that everywhere the algorithms take a function, predicate, or relation, we should add a constraint like <code>IndirectFunction</code>, <code>IndirectPredicate</code>, or <code>IndirectRelation</code>. These concepts will require that the function is callable with a cross-product of values and references, with an extra requirement that the function is also callable with arguments of the common reference type.</p>
  1559. <p>This might seem very strict, but for non-proxy iterators, it adds exactly <em>zero</em> new requirements. And even for proxy iterators, it&#8217;s only saying in code the things that necessarily had to be true anyway. Rather than making things harder, the common reference type makes them <em>easier</em>: if your predicate takes arguments by the common reference type, all the checks succeed, guaranteed.</p>
  1560. <p>It&#8217;s possible that the common reference type is inefficient to use. For instance, the common reference type between <code>bool&amp;</code> and <code>vector&lt;bool&gt;::reference</code> is likely to be a variant type. In that case, you might not want your predicate to take arguments by the common reference. Instead, you&#8217;d want to use a generic lambda, or define a function object with the necessary overloads. The concept checking will tell you if you forgot any overloads, ensuring that your code is correct and portable.</p>
  1561. <h2>Summary</h2>
  1562. <p>That&#8217;s the theory. I implemented all this in my <a href="https://github.com/ericniebler/range-v3">Range-v3</a> library. Now I can <code>sort</code> a <code>zip</code> range of <code>unique_ptr</code>s. So cool.</p>
  1563. <p>Here, in short, are the changes we would need to make the STL fully support proxy iterators:</p>
  1564. <ol>
  1565. <li>The algorithms need to use <code>iter_swap</code> consistently whenever elements need to be swapped. <code>iter_swap</code> should be a documented customization point.</li>
  1566. <li>We need an <code>iter_move</code> customization point so that elements can be moved out of and back into sequence. This gives iterators a new <code>rvalue_reference</code> associated type.</li>
  1567. <li>We need a new <code>common_reference</code> trait that, like <code>common_type</code>, can be specialized on user-defined types.</li>
  1568. <li>All iterators need to guarantee that their <code>value_type</code> and <code>reference</code> associated types share a common reference. Likewise for <code>value_type</code>/<code>rvalue_reference</code>, and for <code>reference</code>/<code>rvalue_reference</code>.</li>
  1569. <li>We need <code>IndirectFunction</code>, <code>IndirectPredicate</code>, and <code>IndirectRelation</code> concepts as described above. The higher-order algorithms should be constrained with them.</li>
  1570. </ol>
  1571. <p>From the end users&#8217; perspective, not a lot changes. All existing code works as it did before, and all iterators that are valid today continue being valid in the future. Some proxy iterators, like <code>vector&lt;bool&gt;</code>&#8216;s, would need some small changes to model the Iterator concept, but afterward those iterators are on equal footing with all the other iterators for the first time ever. Code that deals with proxy sequences might need to use <code>common_reference</code> when defining predicates, or they might need to use a generic lambda instead.</p>
  1572. <p>So that&#8217;s it. To the best of my knowledge, this is the first comprehensive solution to the proxy iterator problem, a problem we&#8217;ve lived with from day one, and which only promises to get worse with the introduction of range views. There&#8217;s some complexity for sure, but the complexity seems to be necessary and inherent. And honestly I don&#8217;t think it&#8217;s all that bad.</p>
  1573. <h2>Future Directions</h2>
  1574. <p>I&#8217;m unsure where this goes from here. I plan to sit on it for a bit to see if any better solutions come along. There&#8217;s been some murmuring about a possible language solution for proxy references, but there is inherent complexity to proxy iterators, and it&#8217;s not clear to me at this point how a language solution would help.</p>
  1575. <p>I&#8217;m currently working on what I believe will be the first draft of a Ranges TS. That paper will not address the proxy iterator problem. I could imagine writing a future paper that proposes the changes I suggest above. Before I do that, I would probably try to start a discussion on the committee mailing lists to feel people out. If any committee members are reading this, feel free to comment below.</p>
  1576. <p>Thanks for following along, and thanks for all your encouraging and thought-provoking comments. Things in the C++ world are moving fast these days. It&#8217;s tough to keep up with it all. I feel blessed that you all have invested so much time exploring these issues with me. &lt;3</p>
  1577. <p>As always, you can find all code described here in my <a href="https://github.com/ericniebler/range-v3">range-v3</a> repo on github.</p>
  1578. <div style="display:none">
  1579. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  1580. </div>
  1581. ]]></content:encoded>
  1582. <wfw:commentRss>https://ericniebler.com/2015/03/03/iterators-plus-plus-part-3/feed/</wfw:commentRss>
  1583. <slash:comments>30</slash:comments>
  1584. <post-id xmlns="com-wordpress:feed-additions:1">918</post-id> </item>
  1585. <item>
  1586. <title>Iterators++, Part 2</title>
  1587. <link>https://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=iterators-plus-plus-part-2</link>
  1588. <comments>https://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/#comments</comments>
  1589. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  1590. <pubDate>Sat, 14 Feb 2015 04:09:31 +0000</pubDate>
  1591. <category><![CDATA[generic-programming]]></category>
  1592. <category><![CDATA[library-design]]></category>
  1593. <category><![CDATA[ranges]]></category>
  1594. <category><![CDATA[std]]></category>
  1595. <guid isPermaLink="false">http://104.154.63.30/?p=874</guid>
  1596.  
  1597. <description><![CDATA[Disclaimer: This is a long, boring post about minutia. For serious library wonks only. This is the third in a series about proxy iterators, the limitations of the existing STL iterator concept hierarchy, and what could be done about it. <a class="more-link" href="https://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/">Continue reading <span class="screen-reader-text">  Iterators++, Part 2</span><span class="meta-nav">&#8594;</span></a>]]></description>
  1598. <content:encoded><![CDATA[<p><em>Disclaimer:</em> This is a long, boring post about minutia. For serious library wonks only.</p>
  1599. <p>This is the third in a series about <strong>proxy iterators</strong>, the limitations of the existing STL iterator concept hierarchy, and what could be done about it. In the <a href="http://104.154.63.30/2015/01/28/to-be-or-not-to-be-an-iterator/">first post</a> I explained what proxy iterators are (an iterator like <code>vector&lt;bool&gt;</code>&#8216;s that, when dereferenced, returns a proxy object rather than a real reference) and three specific difficulties they cause in today&#8217;s STL:</p>
  1600. <ol>
  1601. <li>What, if anything, can we say in general about the relationship between an iterator&#8217;s value type and its reference type?</li>
  1602. <li>How do we constrain higher-order algorithms like <code>for_each</code> and <code>find_if</code> that take functions that operate on a sequence&#8217;s elements?</li>
  1603. <li>How do we implement algorithms that must swap and move elements around, like <code>sort</code> and <code>reverse</code>?</li>
  1604. </ol>
  1605. <p>In the <a href="http://104.154.63.30/2015/02/03/iterators-plus-plus-part-1/">second post</a>, I zoomed in on the problem (3) and showed how the existing <code>std::iter_swap</code> API could be pressed into service, along with a new API that I propose: <code>std::iter_move</code>. Together, these APIs give an iterator a channel through which to communicate to the algorithms how its elements should be swapped and moved. With the addition of the <code>iter_move</code> API, iterators pick up a new <strong>associated type</strong>: <code>rvalue_reference</code>, which can live in <code>std::iterator_traits</code> alongside the existing <code>value_type</code> and <code>reference</code> associated types.</p>
  1606. <p>In this post, I&#8217;ll dig into the first problem: how we define in code what an iterator <em>is</em>.</p>
  1607. <h2>Values and References</h2>
  1608. <p>As in the first two articles, I&#8217;ll use the <code>zip</code> view to motivate the discussion, because it&#8217;s easy to grok and yet totally bedeviling for the STL algorithms. Recall that <code>zip</code> lazily adapts two sequences by making them look like one sequence of <code>pair</code>s, as demonstrated below:</p>
  1609. <pre class="brush: cpp; notranslate">std::vector&lt;int&gt; x{1,2,3,4};
  1610. std::vector&lt;int&gt; y{9,8,7,6};
  1611.  
  1612. using namespace ranges;
  1613. auto zipped = view::zip(x, y);
  1614.  
  1615. assert(*zipped.begin() == std::make_pair(1,9));
  1616. assert(&amp;(*zipped.begin()).first == &amp;x[0]);
  1617. </pre>
  1618. <p>As the two assertions above show, dereferencing a <code>zip</code> iterator yields a <code>pair</code>, and that the pair is actually a pair of <em>references</em>, pointing into the underlying sequences. The <code>zip</code> range above has the following associated types:</p>
  1619. <table>
  1620. <thead>
  1621. <tr>
  1622. <th>Associated type&#8230;</th>
  1623. <th>&#8230; for the <code>zip</code> view</th>
  1624. </tr>
  1625. </thead>
  1626. <tbody>
  1627. <tr>
  1628. <td><code>value_type</code></td>
  1629. <td><code>pair&lt;int, int&gt;</code></td>
  1630. </tr>
  1631. <tr>
  1632. <td><code>reference</code></td>
  1633. <td><code>pair&lt;int &amp;, int &amp;&gt;</code></td>
  1634. </tr>
  1635. <tr>
  1636. <td><code>rvalue_reference</code></td>
  1637. <td><code>pair&lt;int &amp;&amp;, int &amp;&amp;&gt;</code></td>
  1638. </tr>
  1639. </tbody>
  1640. </table>
  1641. <p>With Concepts coming to C++, we&#8217;re going to need to say in code what an iterator <em>is</em>. The <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf"><strong>Palo Alto TR</strong></a>, published in 2012, takes a stab at it: an <code>InputIterator</code> is <code>Readable</code> and <code>Incrementable</code>, where <code>Readable</code> is defined as follows:</p>
  1642. <pre class="brush: cpp; notranslate">template&lt; typename I &gt;
  1643. concept bool Readable =
  1644.    Semiregular&lt;I&gt; &amp;&amp;
  1645.    requires(I i) {
  1646.        typename ValueType&lt;I&gt;;
  1647.        { *i } -&gt; const ValueType&lt;I&gt; &amp;;
  1648.    };
  1649. </pre>
  1650. <p>This says that a <code>Readable</code> type has an associated <code>ValueType</code>. It also says that <code>*i</code> is a <strong>valid expression</strong>, and that the result of <code>*i</code> must be convertible to <code>const ValueType&lt;I&gt; &amp;</code>. This is fine when <code>*i</code> returns something simple like a real reference. But when it returns a proxy reference, like the <code>zip</code> view does, it causes problems.</p>
  1651. <p>Substituting a <code>zip</code> iterator into the <code>requires</code> clause above results in something like this:</p>
  1652. <pre class="brush: cpp; notranslate">const pair&lt;int,int&gt;&amp; x = *i;
  1653. </pre>
  1654. <p>This tries to initialize <code>x</code> with a <code>pair&lt;int&amp;, int&amp;&gt;</code>. This actually works in a sense; the temporary <code>pair&lt;int &amp;, int &amp;&gt;</code> object is implicitly converted into a temporary <code>pair&lt;int, int&gt;</code> by copying the underlying integers, and that new pair is bound to the <code>const &amp;</code> because temporaries can bind to const references.</p>
  1655. <p>But copying values is not what we want or expect. If instead of <code>int</code>s, we had pairs of some move-only type like <code>unique_ptr</code>, this wouldn&#8217;t have worked at all.</p>
  1656. <p>So the <code>Readable</code> concept needs to be tweaked to handle proxy references. What can we do?</p>
  1657. <p>One simple way to make the <code>zip</code> iterator model the <code>Readable</code> concept is to simply remove the requirement that <code>*i</code> be convertible to <code>const ValueType&lt;I&gt;&amp;</code>. This is unsatisfying. Surely there is <em>something</em> we can say about the relationship between an iterator&#8217;s reference type and its value type. I think there is, and there&#8217;s a hint in the way the Palo Alto TR defines the <code>EqualityComparable</code> constraint.</p>
  1658. <h2>Common Type Constraints</h2>
  1659. <p>What do you think about code like this?</p>
  1660. <pre class="brush: cpp; notranslate">vector&lt;string&gt; strs{"three", "blind", "mice"};
  1661. auto it = find(strs.begin(), strs.end(), "mice");
  1662. </pre>
  1663. <p>Seems reasonable, right? This searches a range of <code>string</code>&#8216;s for a <code>char const*</code>. This should this work, even though it&#8217;s looking for an orange in a bucket of apples. The orange is sufficiently apple-like, and because we know how to compare apples and oranges; i.e., there is an <code>operator==</code> that compares <code>string</code>s with <code>char const*</code>. But what does &#8220;sufficiently apple-like&#8221; mean? If we are ever to constrain the <code>find</code> algorithm with Concepts, we need to be able to say in code what &#8220;apple-like&#8221; means for <em>any</em> apple and <em>any</em> orange.</p>
  1664. <p>The Palo Alto TR doesn&#8217;t think that the mere existence of an <code>operator==</code> is enough. Instead, it defines the <em>cross-type <code>EqualityComparable</code> concept</em> as follows:</p>
  1665. <pre class="brush: cpp; notranslate">template&lt; typename T1, typename T2 &gt;
  1666. concept bool EqualityComparable =
  1667.    EqualityComparable&lt;T1&gt; &amp;&amp;
  1668.    EqualityComparable&lt;T2&gt; &amp;&amp;
  1669.    Common&lt;T1, T2&gt; &amp;&amp;
  1670.    EqualityComparable&lt; std::common_type_t&lt;T1, T2&gt; &gt; &amp;&amp;
  1671.    requires(T1 a, T2 b) {
  1672.        { a == b } -&gt; bool;
  1673.        { b == a } -&gt; bool;
  1674.        { a != b } -&gt; bool;
  1675.        { b != a } -&gt; bool;
  1676.        /* axioms:
  1677.            using C = std::common_type_t&lt;T1, T2&gt;;
  1678.            a == b &lt;=&gt; C{a} == C{b};
  1679.            a != b &lt;=&gt; C{a} != C{b};
  1680.            b == a &lt;=&gt; C{b} == C{a};
  1681.            b != a &lt;=&gt; C{b} != C{a};
  1682.        */
  1683.    };
  1684. </pre>
  1685. <p>In words, what this says is for two <em>different</em> types to be EqualityComparable, they each individually must be EqualityComparable (i.e., with themselves), they must be comparable with each other, <em>and</em> (the key bit) they must share a <em>common type</em> which is also EqualityComparable, with identical semantics.</p>
  1686. <p>The question then becomes: do <code>std::string</code> and <code>char const *</code> share a common type, to which they can both be converted, and which compares with the same semantics? In this case, the answer is trivial: <code>std::string</code> is the common type.</p>
  1687. <p>Aside: why does the Palo Alto TR place this extra CommonType requirement on the argument to <code>find</code> when surely that will break some code that works and is &#8220;correct&#8221; today? It&#8217;s an interesting question. The justification is mathematical and somewhat philosophical: when you compare things for equality, you are asking if they have the same value. Just because someone provides an <code>operator==</code> to compare, say, an <code>Employee</code> with a <code>SocialSecurityNumber</code> doesn&#8217;t make an employee a social security number, or vice versa. If we want to be able to reason mathematically about our code (and we do), we have to be able to substitute like for like. Being able to apply equational reasoning to our programs is a boon, but we have to play by its rules.</p>
  1688. <h2>Readable and Common</h2>
  1689. <p>You may be wondering what any of this have to do with the <code>Readable</code> concept. Let&#8217;s look again at the concept as the Palo Alto TR defines it:</p>
  1690. <pre class="brush: cpp; notranslate">template&lt; typename I &gt;
  1691. concept bool Readable =
  1692.    Semiregular&lt;I&gt; &amp;&amp;
  1693.    requires(I i) {
  1694.        typename ValueType&lt;I&gt;;
  1695.        { *i } -&gt; const ValueType&lt;I&gt; &amp;;
  1696.    };
  1697. </pre>
  1698. <p>To my mind, what this is trying to say is there there is some substitutability, some mathematical equivalence, between an iterator&#8217;s reference type and its value type. <code>EqualityComparable</code> uses <code>Common</code> to enforce that substitutability. What if we tried to fix <code>Readable</code> in a similar way?</p>
  1699. <pre class="brush: cpp; notranslate">template&lt; typename I &gt;
  1700. concept bool Readable =
  1701.    Semiregular&lt;I&gt; &amp;&amp;
  1702.    requires(I i) {
  1703.        typename ValueType&lt;I&gt;;
  1704.        requires Common&lt; ValueType&lt;I&gt;, decltype(*i) &gt;;
  1705.    };
  1706. </pre>
  1707. <p>Here we&#8217;re saying that for <code>Readable</code> types, the reference type and the value type must share a common type. The common type is computed using something like <code>std::common_type_t</code>, which basically uses the ternary conditional operator (<code>?:</code>). (I say &#8220;something like&#8221; since <code>std::common_type_t</code> isn&#8217;t actually up to the task. See <a href="https://cplusplus.github.io/LWG/lwg-defects.html#2408">lwg2408</a> and <a href="https://cplusplus.github.io/LWG/lwg-active.html#2465">lwg2465</a>.)</p>
  1708. <p>Sadly, this doesn&#8217;t quite solve the problem. If you try to do <code>common_type_t&lt;unique_ptr&lt;int&gt;, unique_ptr&lt;int&gt;&amp;&gt;</code> you&#8217;ll see why. It doesn&#8217;t work, despite the fact that the answer seems obvious. The trouble is that <code>common_type</code> always strips top-level const and reference qualifiers before testing for the common type with the conditional operator. For move-only types, that causes the conditional operator to barf.</p>
  1709. <p>I&#8217;ve always found it a bit odd that <code>common_type</code> decays its arguments before testing them. Sometimes that&#8217;s what you want, but sometimes (like here) its not. Instead, what we need is a different type trait that test for the common type, but preserves reference and cv qualifications. I call it <code>common_reference</code>. It&#8217;s a bit of a misnomer though, since it doesn&#8217;t always return a reference type, although it might.</p>
  1710. <p>The common reference of two types is the minimally qualified type to which objects of both types can bind. <code>common_reference</code> will try to return a reference type if it can, but fall back to a value type if it must. Here&#8217;s some examples to give you a flavor:</p>
  1711. <table>
  1712. <thead>
  1713. <tr>
  1714. <th>Common reference&#8230;</th>
  1715. <th>&#8230; result</th>
  1716. </tr>
  1717. </thead>
  1718. <tbody>
  1719. <tr>
  1720. <td><code>common_reference_t&lt;int &amp;, int const &amp;&gt;</code></td>
  1721. <td><code>int const &amp;</code></td>
  1722. </tr>
  1723. <tr>
  1724. <td><code>common_reference_t&lt;int &amp;&amp;, int &amp;&amp;&gt;</code></td>
  1725. <td><code>int &amp;&amp;</code></td>
  1726. </tr>
  1727. <tr>
  1728. <td><code>common_reference_t&lt;int &amp;&amp;, int &amp;&gt;</code></td>
  1729. <td><code>int const &amp;</code></td>
  1730. </tr>
  1731. <tr>
  1732. <td><code>common_reference_t&lt;int &amp;, int&gt;</code></td>
  1733. <td><code>int</code></td>
  1734. </tr>
  1735. </tbody>
  1736. </table>
  1737. <p>With a <code>common_reference</code> type trait, we could define a <code>CommonReference</code> concept and specify <code>Readable</code> in terms of it, as follows:</p>
  1738. <pre class="brush: cpp; notranslate">template&lt; typename I &gt;
  1739. concept bool Readable =
  1740.    Semiregular&lt;I&gt; &amp;&amp;
  1741.    requires(I i) {
  1742.        typename ValueType&lt;I&gt;;
  1743.        requires CommonReference&lt;
  1744.            ValueType&lt;I&gt; &amp;,
  1745.            decltype(*i) &amp;&amp; &gt;;
  1746.    };
  1747. </pre>
  1748. <p>The above concept requires that there is some common reference type to which both <code>*i</code> and a mutable object of the iterator&#8217;s value type can bind.</p>
  1749. <p>This, I think, is sufficiently general to type check all the iterators that are valid today, as well as iterators that return proxy references (though it takes some work to see that). We can further generalize this to accommodate the <code>iter_move</code> API I described in my previous post:</p>
  1750. <pre class="brush: cpp; notranslate">template&lt; typename I &gt;
  1751. concept bool Readable =
  1752.    Semiregular&lt;I&gt; &amp;&amp;
  1753.    requires(I i) {
  1754.        typename ValueType&lt;I&gt;;
  1755.        requires CommonReference&lt;
  1756.            ValueType&lt;I&gt; &amp;,
  1757.            decltype(*i) &amp;&amp; &gt;;          // (1)
  1758.        requires CommonReference&lt;
  1759.            decltype(iter_move(i)) &amp;&amp;,
  1760.            decltype(*i) &amp;&amp; &gt;;          // (2)
  1761.        requires CommonReference&lt;
  1762.            ValueType&lt;I&gt; const &amp;,
  1763.            decltype(iter_move(i)) &amp;&amp;&gt;; // (3)
  1764.    };
  1765. </pre>
  1766. <p>OK, let&#8217;s see how this works in practice.</p>
  1767. <h2>Iterators and CommonReference</h2>
  1768. <p>First, let&#8217;s take the easy case of an iterator that returns a real reference like <code>int&amp;</code>. The requirements are that its value type, reference type, and rvalue reference type satisfy the three <code>CommonReference</code> constraints above. (1) requires a common reference between <code>int&amp;</code> and <code>int&amp;</code>. (2), between <code>int&amp;&amp;</code> and <code>int&amp;</code>, and (3) between <code>int const&amp;</code> and <code>int&amp;&amp;</code>. These are all demonstrably true, so this iterator is <code>Readable</code>.</p>
  1769. <p>But what about the <code>zip</code> iterator? Things here are much trickier.</p>
  1770. <p>The three common reference constraints for the <code>zip</code> iterator amount to this:</p>
  1771. <table>
  1772. <thead>
  1773. <tr>
  1774. <th>Common reference&#8230;</th>
  1775. <th>&#8230; result</th>
  1776. </tr>
  1777. </thead>
  1778. <tbody>
  1779. <tr>
  1780. <td><code>common_reference_t&lt;</code> <br /> <code>pair&lt;int,int&gt; &amp;,</code> <br /> <code>pair&lt;int&amp;,int&amp;&gt; &amp;&amp;&gt;</code></td>
  1781. <td>???</td>
  1782. </tr>
  1783. <tr>
  1784. <td><code>common_reference_t&lt;</code> <br /> <code>pair&lt;int&amp;&amp;,int&amp;&amp;&gt; &amp;&amp;,</code> <br /> <code>pair&lt;int&amp;,int&amp;&gt; &amp;&amp;&gt;</code></td>
  1785. <td>???</td>
  1786. </tr>
  1787. <tr>
  1788. <td><code>common_reference_t&lt;</code>  <br /> <code>pair&lt;int,int&gt; const &amp;,</code> <br /> <code>pair&lt;int&amp;&amp;,int&amp;&amp;&gt; &amp;&amp;&gt;</code></td>
  1789. <td>???</td>
  1790. </tr>
  1791. </tbody>
  1792. </table>
  1793. <p>Yikes. How is the <code>common_reference</code> trait supposed to evaluate this? The ternary conditional operator is just not up to the task.</p>
  1794. <p>OK, let&#8217;s first imagine what we would like the answers to be. Taking the last one first, consider the following code:</p>
  1795. <pre class="brush: cpp; notranslate">void foo( pair&lt; X, Y &gt; p );
  1796.  
  1797. pair&lt;int,int&gt; const &amp; a = /*...*/;
  1798. pair&lt;int &amp;&amp;,int &amp;&amp;&gt; b {/*...*/};
  1799.  
  1800. foo( a );
  1801. foo( move(b) );
  1802. </pre>
  1803. <p>If there are types that we can pick for <code>X</code> and <code>Y</code> that make this compile, then we can make <code>pair&lt;X,Y&gt;</code> the &#8220;common reference&#8221; for <code>pair&lt;int&amp;&amp;,int&amp;&amp;&gt;&amp;&amp;</code> and <code>pair&lt;int,int&gt; const &amp;</code>. Indeed there are: <code>X</code> and <code>Y</code> should both be <code>int const &amp;</code>.</p>
  1804. <p>In fact, for each of the <code>CommonReference</code> constraints, we could make the answer <code>pair&lt;int const&amp;,int const&amp;&gt;</code> and be safe. So in principle, our <code>zip</code> iterator <em>can</em> model the <code>Readable</code> concept. W00t.</p>
  1805. <p>But look again at this one:</p>
  1806. <pre class="brush: cpp; notranslate">common_reference_t&lt;pair&lt;int,int&gt; &amp;, pair&lt;int&amp;,int&amp;&gt; &amp;&amp;&gt;
  1807. </pre>
  1808. <p>If this coughs up <code>pair&lt;int const&amp;,int const&amp;&gt;</code> then we&#8217;ve lost something in the translation: the ability to mutate the elements of the pair. In an ideal world, the answer would be <code>pair&lt;int&amp;,int&amp;&gt;</code> because a conversion from both <code>pair&lt;int,int&gt;&amp;</code> and <code>pair&lt;int&amp;,int&amp;&gt;&amp;&amp;</code> would be safe and meets the &#8220;minimally qualified&#8221; spirit of the <code>common_reference</code> trait. But this code doesn&#8217;t compile:</p>
  1809. <pre class="brush: cpp; notranslate">void foo( pair&lt; int&amp;,int&amp; &gt; p );
  1810.  
  1811. pair&lt;int,int&gt; a;
  1812. pair&lt;int&amp;,int&amp;&gt; b {/*...*/};
  1813.  
  1814. foo( a );       // ERROR here
  1815. foo( move(b) );
  1816. </pre>
  1817. <p>Unfortunately, <code>pair</code> doesn&#8217;t provide this conversion, even though it would be safe in theory. Is that a defect? Perhaps. But it&#8217;s something we need to work with.</p>
  1818. <p>Long story short, the solution I went with for range-v3 is to define my own <code>pair</code>-like type with the needed conversions. I call it <code>common_pair</code> and it inherits from <code>std::pair</code> so that things behave as you would expect. With <code>common_pair</code> and a few crafty specializations of <code>common_reference</code>, the <code>Readable</code> constraints are satisfied for the <code>zip</code> iterator as follows:</p>
  1819. <table>
  1820. <thead>
  1821. <tr>
  1822. <th>Common reference&#8230;</th>
  1823. <th>&#8230; result</th>
  1824. </tr>
  1825. </thead>
  1826. <tbody>
  1827. <tr>
  1828. <td><code>common_reference_t&lt;</code>  <br /> <code>pair&lt;int,int&gt; &amp;,</code> <br /> <code>common_pair&lt;int&amp;,int&amp;&gt; &amp;&amp;&gt;</code></td>
  1829. <td><code>common_pair&lt;int&amp;,int&amp;&gt;</code></td>
  1830. </tr>
  1831. <tr>
  1832. <td><code>common_reference_t&lt;</code><br /> <code>common_pair&lt;int&amp;&amp;,int&amp;&amp;&gt; &amp;&amp;,</code> <br /> <code>common_pair&lt;int&amp;,int&amp;&gt; &amp;&amp;&gt;</code></td>
  1833. <td><code>common_pair&lt;int const&amp;,int const&amp;&gt;</code></td>
  1834. </tr>
  1835. <tr>
  1836. <td><code>common_reference_t&lt;</code>  <br /> <code>pair&lt;int,int&gt; const &amp;,</code> <br /> <code>common_pair&lt;int&amp;&amp;,int&amp;&amp;&gt; &amp;&amp;&gt;</code></td>
  1837. <td><code>common_pair&lt;int const&amp;,int const&amp;&gt;</code></td>
  1838. </tr>
  1839. </tbody>
  1840. </table>
  1841. <p>Computing these types is not as tricky as it may appear at first. For types like <code>pair&lt;int,int&gt;&amp;</code> and <code>common_pair&lt;int&amp;,int&amp;&gt;&amp;&amp;</code>, it goes like this:</p>
  1842. <ol>
  1843. <li>Distribute any top-level ref and cv qualifiers to the members of the pair. <code>pair&lt;int,int&gt;&amp;</code> becomes <code>pair&lt;int&amp;,int&amp;&gt;</code>, and <code>common_pair&lt;int&amp;,int&amp;&gt;&amp;&amp;</code> becomes <code>common_pair&lt;int&amp;,int&amp;&gt;</code>.</li>
  1844. <li>Compute the element-wise common reference, and bundle the result into a new <code>common_pair</code>, resulting in <code>common_pair&lt;int&amp;,int&amp;&gt;</code>.</li>
  1845. </ol>
  1846. <h2>Generalizing</h2>
  1847. <p>Our <code>zip</code> iterator, with enough ugly hackery, can model our re-specified <code>Readable</code> concept. That&#8217;s good, but what about other proxy reference types, like <code>vector&lt;bool&gt;</code>&#8216;s? If <code>vector&lt;bool&gt;</code>&#8216;s reference type is <code>bool_ref</code>, then we would need to specialize <code>common_reference</code> such that the <code>Readable</code> constraints are satisfied. This will necessarily involve defining a type such that it can be initialized with either a <code>bool_ref</code> or with a <code>bool&amp;</code>. That would be a decidedly weird type, but it&#8217;s not impossible. (Imagine a <code>variant&lt;bool&amp;,bool_ref&gt;</code> if you&#8217;re having trouble visualizing it.)</p>
  1848. <p>Getting <code>vector&lt;bool&gt;</code>&#8216;s iterators to fit the mold is an ugly exercise in hackery, and actually <em>using</em> its common reference (the variant type) would incur a performance hit for every read and write. But the STL doesn&#8217;t actually need to use it. It just needs to exist.</p>
  1849. <p>What is the point of jumping through these hoops to implement an inefficient type that in all likelihood will never actually be <em>used</em>? This is going to be unsatisfying for many, but the answer is for the sake of mathematical rigour. There must be some substitutability relationship between an iterator&#8217;s reference type and its value type that is enforceable. Requiring that they share a common reference is the best I&#8217;ve come up with so far. And as it turns out, this &#8220;useless&#8221; type actually does have some uses, as we&#8217;ll see in the next installment.</p>
  1850. <h2>Summary</h2>
  1851. <p>So here we are. There <em>is</em> a way to define the <code>Readable</code> concept &#8212; and hence the <code>InputIterator</code> concept &#8212; in a way that is general enough to permit proxy iterators while also saying something meaningful and useful about an iterator&#8217;s associated types. Actually defining a proxy iterator such that it models this concept is no small feat and requires extensive amounts of hack work. BUT IT&#8217;S POSSIBLE.</p>
  1852. <p>One could even imagine defining a Universal Proxy Reference type that takes a getter and setter function and does all the hoop jumping to satisfy the Iterator concepts &#8212; one proxy reference to rule them all, if you will. That&#8217;s left as an exercise for the reader.</p>
  1853. <p>If you made it this far, congratulations. You could be forgiven for feeling a little let down; this solution is far from ideal. Perhaps it&#8217;s just awful enough to spur a real discussion about how we could change the language to improve the situation.</p>
  1854. <p>In the next installment, I&#8217;ll describe the final piece of the puzzle: how do we write the algorithm constraints such that they permit proxy iterators? Stay tuned.</p>
  1855. <p>As always, you can find all code described here in my <a href="https://github.com/ericniebler/range-v3">range-v3</a> repo on github.</p>
  1856. <div style="display:none">
  1857. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  1858. </div>
  1859. ]]></content:encoded>
  1860. <wfw:commentRss>https://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/feed/</wfw:commentRss>
  1861. <slash:comments>62</slash:comments>
  1862. <post-id xmlns="com-wordpress:feed-additions:1">874</post-id> </item>
  1863. <item>
  1864. <title>Iterators++, Part 1</title>
  1865. <link>https://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=iterators-plus-plus-part-1</link>
  1866. <comments>https://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/#comments</comments>
  1867. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  1868. <pubDate>Wed, 04 Feb 2015 03:31:43 +0000</pubDate>
  1869. <category><![CDATA[generic-programming]]></category>
  1870. <category><![CDATA[library-design]]></category>
  1871. <category><![CDATA[ranges]]></category>
  1872. <category><![CDATA[std]]></category>
  1873. <guid isPermaLink="false">http://104.154.63.30/?p=856</guid>
  1874.  
  1875. <description><![CDATA[In the last post, I described the so-called proxy iterator problem: the fact that iterators that return proxy references instead of real references don&#8217;t sit comfortably within the STL&#8217;s framework. Real, interesting, and useful iterators fall foul of this line, <a class="more-link" href="https://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/">Continue reading <span class="screen-reader-text">  Iterators++, Part 1</span><span class="meta-nav">&#8594;</span></a>]]></description>
  1876. <content:encoded><![CDATA[<p>In the <a href="http://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/">last post</a>, I described the so-called proxy iterator problem: the fact that iterators that return proxy references instead of real references don&#8217;t sit comfortably within the STL&#8217;s framework. Real, interesting, and useful iterators fall foul of this line, iterators like <code>vector&lt;bool&gt;</code>&#8216;s or like the iterator of the <code>zip</code> view I presented. In this post, I investigate what we could do to bring proxy iterators into the fold &#8212; what it means for both the iterator concepts and for the algorithms. Since I&#8217;m a library guy, I restrict myself to talking about pure library changes.</p>
  1877. <h1>Recap</h1>
  1878. <p>As in the last post, we&#8217;ll use the <code>zip</code> view to motivate the discussion. Given two sequences like:</p>
  1879. <pre class="brush: cpp; notranslate">vector&lt;int&gt; x{1,2,3,4};
  1880. vector&lt;int&gt; y{9,8,7,6};
  1881. </pre>
  1882. <p>&#8230;we can create a view by &#8220;zipping&#8221; the two into one, where each element of the view is a pair of corresponding elements from <code>x</code> and <code>y</code>:</p>
  1883. <pre class="brush: cpp; notranslate">using namespace ranges;
  1884. auto rng = view::zip(x, y);
  1885.  
  1886. assert(*rng.begin() == make_pair(1,9));
  1887. </pre>
  1888. <p>The type of the expression &#8220;<code>*rng.begin()</code>&#8221; &#8212; the range&#8217;s <em>reference type</em> &#8212; is <code>pair&lt;int&amp;,int&amp;&gt;</code>, and the range&#8217;s value type is <code>pair&lt;int,int&gt;</code>. The reference type is an example of a <strong>proxy</strong>: an object that stands in for another object, or in this case two other objects.</p>
  1889. <p>Since both <code>x</code> and <code>y</code> are random access, the resulting <code>zip</code> view should be random access, too. But here we run foul of STL&#8217;s &#8220;real reference&#8221; requirement: for iterators other than input iterators, the expression <code>*it</code> <em>must</em> return a real reference. Why? Good question! The requirement was added sometime while the STL was being standardized. I can only guess it was because the committee didn&#8217;t know what it meant to, say, sort or reverse elements that aren&#8217;t themselves persistent in memory, and they didn&#8217;t know how to communicate to the algorithms that a certain temporary object (the proxy) is a stand-in for a persistent object. (Maybe someone who was around then can confirm or deny.)</p>
  1890. <p>The real-reference requirement is quite restrictive. Not only does it mean the <code>zip</code> view can&#8217;t be a random access sequence, it also means that you can&#8217;t sort or reverse elements through a <code>zip</code> view. It&#8217;s also the reason why <a href="http://www.gotw.ca/publications/mill09.htm"><code>vector&lt;bool&gt;</code> is not a real container</a>.</p>
  1891. <p>But simply dropping the real-reference requirement isn&#8217;t enough. We also need to say what it means to sort and reverse sequences that don&#8217;t yield real references. In the last post, I described three specific problems relating to constraining and implementing algorithms in the presence of proxy references.</p>
  1892. <ol>
  1893. <li>What, if anything, can we say about the relationship between an iterator&#8217;s value type and its reference type?</li>
  1894. <li>How do we constrain higher-order algorithms like <code>for_each</code> and <code>find_if</code> that take functions that operate on a sequence&#8217;s elements?</li>
  1895. <li>How do we implement algorithms that must swap and move elements around, like <code>sort</code>?</li>
  1896. </ol>
  1897. <p>Let&#8217;s take the last one first.</p>
  1898. <h2>Swapping and Moving Elements</h2>
  1899. <p>If somebody asked you in a job interview to implement <code>std::reverse</code>, you might write something like this:</p>
  1900. <pre class="brush: cpp; notranslate">template&lt; class BidiIter &gt;
  1901. void reverse( BidiIter begin, BidiIter end )
  1902. {
  1903.    using std::swap;
  1904.    for(; begin != end &amp;&amp; begin != --end; ++begin)
  1905.        swap(*begin, *end);
  1906. }
  1907. </pre>
  1908. <p>Congratulations, you&#8217;re hired. Now, if the interviewer asked you whether this algorithm works on the <code>zip</code> view I just described, what would you say? The answer, as you may have guessed, is no. There is no overload of <code>swap</code> that accepts <code>pair</code> rvalues. Even if there were, we&#8217;re on thin ice here with the <code>zip</code> view&#8217;s proxy reference type. The default <code>swap</code> implementation looks like this:</p>
  1909. <pre class="brush: cpp; notranslate">template&lt; class T &gt;
  1910. void swap( T &amp; t, T &amp; u )
  1911. {
  1912.    T tmp = move(u);
  1913.    u = move(t);
  1914.    t = move(tmp);
  1915. }
  1916. </pre>
  1917. <p>Imagine what happens when <code>T</code> is <code>pair&lt;int&amp;,int&amp;&gt;</code>. The first line doesn&#8217;t move any values; <code>tmp</code> just aliases the values referred to by <code>u</code>. The next line stomps the values in <code>u</code>, which mutates <code>tmp</code> because it&#8217;s an alias. Then we copy those stomped values back to <code>t</code>. Rather than swapping values, this makes them both equal to <code>t</code>. Oops.</p>
  1918. <p>If at this point you&#8217;re smugly saying to yourself that <code>pair</code> has its own <code>swap</code> overload that (almost) does the right thing, you&#8217;re very smart. Shut up. But if you&#8217;re saying that the above is not a standard-conforming <code>reverse</code> implementation because, unlike all the other algorithms, <code>reverse</code> is required to use <code>iter_swap</code>, then very good! That&#8217;s the clue to unraveling this whole mess.</p>
  1919. <h2>iter_swap</h2>
  1920. <p><code>iter_swap</code> is a thin wrapper around <code>swap</code> that takes iterators instead of values and swaps the elements they refer to. It&#8217;s an exceedingly useless function, since <code>iter_swap(a,b)</code> is pretty much required to just call <code>swap(*a,*b)</code>. But what if we allowed it to be a bit smarter? What if <code>iter_swap</code> were a full-fledged <a href="http://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/">customization point</a> that allowed proxied sequences to communicate to the algorithms how their elements should be swapped?</p>
  1921. <p>Imagine the <code>zip</code> view&#8217;s iterators provided an <code>iter_swap</code> that knew how to truly swap the elements in the underlying sequences. It might look like this:</p>
  1922. <pre class="brush: cpp; notranslate">template&lt; class It1, class It2 &gt;
  1923. struct zip_iterator
  1924. {
  1925.    It1 it1;
  1926.    It2 it2;
  1927.  
  1928.    /* ... iterator interface here... */
  1929.  
  1930.    friend void iter_swap(zip_iterator a, zip_iterator b)
  1931.    {
  1932.        using std::iter_swap;
  1933.        iter_swap(a.it1, b.it1);
  1934.        iter_swap(a.it2, b.it2);
  1935.    }
  1936. };
  1937. </pre>
  1938. <p>Now we would implement <code>reverse</code> like this:</p>
  1939. <pre class="brush: cpp; notranslate">template&lt; class BidiIter &gt;
  1940. void reverse( BidiIter begin, BidiIter end )
  1941. {
  1942.    using std::iter_swap;
  1943.    for(; begin != end &amp;&amp; begin != --end; ++begin)
  1944.        iter_swap(begin, end);
  1945. }
  1946. </pre>
  1947. <p><em>Voilà!</em> Now <code>reverse</code> works with <code>zip</code> views. That was easy. All that is required is (a) to advertise <code>iter_swap</code> as a customization point, and (b) use <code>iter_swap</code> consistently throughout the standard library, not just in <code>reverse</code>.</p>
  1948. <h2>iter_move</h2>
  1949. <p>We haven&#8217;t fixed the problem yet. Some algorithms don&#8217;t just swap elements; they move them. For instance <code>stable_sort</code> might allocate a temporary buffer and move elements into it while it works. You can&#8217;t use <code>iter_swap</code> to move an element into raw storage. But we can use a play from the <code>iter_swap</code> playbook to solve this problem. Let&#8217;s make an <code>iter_move</code> customization point that gives iterators a way to communicate how to move values out of the sequence.</p>
  1950. <p><code>iter_move</code>&#8216;s default implementation is <em>almost</em> trivial:</p>
  1951. <pre class="brush: cpp; notranslate">template&lt; class I,
  1952.    class R = typename iterator_traits&lt; I &gt;::reference &gt;
  1953. conditional_t&lt;
  1954.    is_reference&lt; R &gt;::value,
  1955.    remove_reference_t&lt; R &gt; &amp;&amp;,
  1956.    R &gt;
  1957. iter_move( I it )
  1958. {
  1959.    return move(*it);
  1960. }
  1961. </pre>
  1962. <p>The only tricky bit is the declaration of the return type. If <code>*it</code> returns a temporary, we just want to return it by value. Otherwise, we want to return it by rvalue reference. If you pass a <code>vector&lt;string&gt;::iterator</code> to <code>iter_move</code>, you get back a <code>string &amp;&amp;</code> as you might expect.</p>
  1963. <p>How does the <code>zip</code> view implement <code>iter_move</code>? It&#8217;s not hard at all:</p>
  1964. <pre class="brush: cpp; notranslate">template&lt; class It1, class It2 &gt;
  1965. struct zip_iterator
  1966. {
  1967.    It1 it1;
  1968.    It2 it2;
  1969.  
  1970.    /* ... iterator interface here... */
  1971.  
  1972.    friend auto iter_move(zip_iterator a)
  1973.    {
  1974.        using std::iter_move;
  1975.        using RRef1 = decltype(iter_move(a.it1));
  1976.        using RRef2 = decltype(iter_move(a.it2));
  1977.        return pair&lt;RRef1, RRef2&gt;{
  1978.            iter_move(a.it1),
  1979.            iter_move(a.it2)
  1980.        };
  1981.    }
  1982. };
  1983. </pre>
  1984. <p>The algorithms can use <code>iter_move</code> as follows:</p>
  1985. <pre class="brush: cpp; notranslate">// Move an element out of the sequence and into a temporary
  1986. using V = typename iterator_traits&lt; I &gt;::value_type;
  1987. V tmp = iter_move( it );
  1988. // Move the value back into the sequence
  1989. *it = move( tmp );
  1990. </pre>
  1991. <p>As an aside, this suggests a more general default implementation of <code>iter_swap</code>:</p>
  1992. <pre class="brush: cpp; notranslate">template&lt; class I &gt;
  1993. void iter_swap( I a, I b )
  1994. {
  1995.    using V = typename iterator_traits&lt; I &gt;::value_type;
  1996.    V tmp = iter_move( a );
  1997.    *a = iter_move( b );
  1998.    *b = move( tmp );
  1999. }
  2000. </pre>
  2001. <p>Now proxy sequences like <code>zip</code> only have to define <code>iter_move</code> and they gets a semantically correct <code>iter_swap</code> for free. It&#8217;s analogous to how the default <code>std::swap</code> is defined in terms of <code>std::move</code>. (Doing it this way doesn&#8217;t pick up user-defined overloads of <code>swap</code>. That&#8217;s bad. There&#8217;s a work-around, but it&#8217;s beyond the scope of this post.)</p>
  2002. <p>For a <code>zip</code> view that has value type <code>pair&lt;T,U&gt;</code> and reference type <code>pair&lt;T&amp;,U&amp;&gt;</code>, the return type of <code>iter_move</code> is <code>pair&lt;T&amp;&amp;,U&amp;&amp;&gt;</code>. Makes perfect sense. Take another look at the default implementation of <code>iter_swap</code> above and satisfy yourself that it correctly swaps zipped elements, even if the underlying sequences have move-only value types.</p>
  2003. <p>One final note about <code>iter_move</code>: the implication is that to support proxied sequences, iterators need an extra <strong>associated type</strong>: the return type of <code>iter_move</code>. We can call it <code>rvalue_reference</code> and put it in <code>iterator_traits</code> alongside <code>value_type</code> and <code>reference</code>.</p>
  2004. <h2>Alternate Design</h2>
  2005. <p>I find the above design clean and intuitive. But it raises an interesting question: is it OK that <code>iter_swap(a,b)</code> and <code>swap(*a,*b)</code> might mean different things? Personally I think that&#8217;s OK, but let&#8217;s imagine for a moment that it&#8217;s not. What else could we do?</p>
  2006. <p>An obvious alternate design is to overload <code>swap</code> for proxy references to swap the objects they refer to. Let&#8217;s imagine we add the following overload to namespace <code>std</code>:</p>
  2007. <pre class="brush: cpp; notranslate">template&lt; class T, class U &gt;
  2008. void swap( pair&lt; T&amp;, U&amp; &gt; &amp;&amp; a, pair&lt; T&amp;, U&amp; &gt; &amp;&amp; b )
  2009. {
  2010.    swap(a.first, b.first);
  2011.    swap(a.second, b.second);
  2012. }
  2013. </pre>
  2014. <p>With enough SFINAE magic we could further generalize this to support swapping pairs of proxy references, but let&#8217;s stick with this. I could live with it.</p>
  2015. <p>But as before, this isn&#8217;t enough; we would also need to overload <code>move</code> to take a <code>pair&lt;T&amp;,U&amp;&gt;</code> and return a <code>pair&lt;T&amp;&amp;,U&amp;&amp;&gt;</code>. And this is where I start getting uncomfortable, because <code>move</code> is used everywhere and it&#8217;s currently not a customization point. How much code is out there that assumes the type of a <code>move</code> expression is <tt><em><some-type></em>&amp;&amp;</tt>? What breaks when that&#8217;s no longer true?</p>
  2016. <p>Purely as a matter of library evolution, overloading <code>move</code> that way for pairs of references is a non-starter because it would be changing the meaning of existing code. We could avoid the problem by changing <code>zip</code>&#8216;s reference type from <code>pair&lt;T&amp;,U&amp;&gt;</code> to <code>magic_proxy_pair&lt; T&amp;, U&amp; &gt;</code> and overloading <code>swap</code> and <code>move</code> on that. <code>magic_proxy_pair</code> would inherit from <code>pair</code>, so most code would be none the wiser. Totally valid design.</p>
  2017. <h2>Summary, For Now</h2>
  2018. <p>I&#8217;ve run long at the mouth, and I still have two more issues to deal with, so I&#8217;ll save them for another post. We&#8217;ve covered a lot of ground. With the design suggested above, algorithms can permute elements in proxied sequences with the help of <code>iter_swap</code> and <code>iter_move</code>, and iterators get a brand new associated type called <code>rvalue_reference</code>.</p>
  2019. <p>Whether you prefer this design or the other depends on which you find more distasteful:</p>
  2020. <ol>
  2021. <li><code>iter_swap(a,b)</code> can be semantically different than <code>swap(*a,*b)</code>, <em>or</em></li>
  2022. <li><code>move</code> is a customization point that is allowed to return some proxy rvalue reference type.</li>
  2023. </ol>
  2024. <p>In the next installment, I&#8217;ll describe what we can say about the relationship between an iterator&#8217;s value type and its reference type (and now its rvalue reference type), and how we can constrain higher-order algorithms like <code>for_each</code> and <code>find_if</code>.</p>
  2025. <p>As always, you can find all code described here in my <a href="https://github.com/ericniebler/range-v3">range-v3</a> repo on github.</p>
  2026. <div style="display:none">
  2027. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  2028. </div>
  2029. ]]></content:encoded>
  2030. <wfw:commentRss>https://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/feed/</wfw:commentRss>
  2031. <slash:comments>27</slash:comments>
  2032. <post-id xmlns="com-wordpress:feed-additions:1">856</post-id> </item>
  2033. <item>
  2034. <title>To Be or Not to Be (an Iterator)</title>
  2035. <link>https://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/?utm_source=rss&#038;utm_medium=rss&#038;utm_campaign=to-be-or-not-to-be-an-iterator</link>
  2036. <comments>https://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/#comments</comments>
  2037. <dc:creator><![CDATA[Eric Niebler]]></dc:creator>
  2038. <pubDate>Thu, 29 Jan 2015 06:31:13 +0000</pubDate>
  2039. <category><![CDATA[generic-programming]]></category>
  2040. <category><![CDATA[library-design]]></category>
  2041. <category><![CDATA[ranges]]></category>
  2042. <category><![CDATA[std]]></category>
  2043. <guid isPermaLink="false">http://104.154.63.30/?p=826</guid>
  2044.  
  2045. <description><![CDATA[Way back in 1999, when the ink on the first C++ standard was still damp, Herb Sutter posed a GoTW puzzler in the still extant C++ Report (RIP): When Is a Container Not a Container? In that article, Herb described <a class="more-link" href="https://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/">Continue reading <span class="screen-reader-text">  To Be or Not to Be (an Iterator)</span><span class="meta-nav">&#8594;</span></a>]]></description>
  2046. <content:encoded><![CDATA[<p>Way back in 1999, when the ink on the first C++ standard was still damp, Herb Sutter posed a GoTW puzzler in the still extant <em>C++ Report</em> (RIP): <a href="http://www.gotw.ca/publications/mill09.htm">When Is a Container Not a Container?</a> In that article, Herb described the problems of the now-infamous <code>vector&lt;bool&gt;</code>. According to the standard&#8217;s own container requirements, <code>vector&lt;bool&gt;</code> is <em>not</em> a container.</p>
  2047. <p>In a nutshell, it&#8217;s because <code>vector&lt;bool&gt;</code>&#8216;s iterators claim to be random-access, but they&#8217;re not. Random-access iterators, when you dereference them, <em>must</em> return a real reference. They can only do that if the thing they point to really exists somewhere. But the <code>bool</code> that a <code>vector&lt;bool&gt;::iterator</code> points to does <em>not</em> exist anywhere. It&#8217;s actually a bit in a packed integer, and dereferencing a <code>vector&lt;bool&gt;</code>&#8216;s iterator returns an object of some type that merely acts like a <code>bool&amp;</code> without actually being a <code>bool&amp;</code>.</p>
  2048. <p>Herb goes so far as to say this:</p>
  2049. <blockquote>
  2050. <p>[&#8230;] although a proxied collection can be an important and useful tool, by definition it must violate the standard&#8217;s container requirements and therefore can never be a conforming container.</p>
  2051. </blockquote>
  2052. <p>At the end of his article, Herb suggests that people stop using <code>vector&lt;bool&gt;</code> and use <code>std::bitset</code> if they want bit-packing. But that just pushes the problem around. Why shouldn&#8217;t <code>std::bitset</code> be a conforming container with random-access iterators? If proxied collections are so useful, why should we content ourselves with a standard library that treats them like second-class citizens?</p>
  2053. <h2>A Brief History of Proxy Iterators</h2>
  2054. <p>Herb wrote his article in 1999, so we&#8217;ve been living with this problem for a long time. Many have tried to fix it and ultimately failed for one reason or another. Mostly it&#8217;s because all the solutions have tried to be backwards compatible, shoehorning a <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1640.html">richer iterator hierarchy</a> into a standard that doesn&#8217;t easily allow it, or else <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1873.html">breaking iterators themselves apart</a> into separate objects that control traversal and element access. Each time the committee has balked, preferring instead the devil it knew.</p>
  2055. <p>An interesting historical note: the original STL design didn&#8217;t have the &#8220;true reference&#8221; requirement that causes the problem. Take a look at the SGI docs for the <a href="https://www.sgi.com/tech/stl/ForwardIterator.html">Forward Iterator</a> concept. Nowhere does it say that <code>*it</code> should be a real reference. The docs for <a href="https://www.sgi.com/tech/stl/trivial.html">Trivial Iterators</a> specifically mention proxy references and say they&#8217;re legit.</p>
  2056. <p>Recently, a who&#8217;s who of C++ luminaries put their names on <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf">N3351</a>, the so-called <strong>Palo Alto TR</strong>, which proposes a concept-based redesign of the STL, using the syntax of Concepts Lite. Interestingly, the Palo Alto TR is a throw-back to the original SGI design: there is no &#8220;true-reference&#8221; requirement on the return type of <code>*it</code>; it merely must be convertible to <code>const ValueType&lt;I&gt; &amp;</code>:</p>
  2057. <pre class="brush: cpp; notranslate">// This must work, according to the Palo Alto TR
  2058. const ValueType&lt;I&gt; &amp; val = *it;
  2059. </pre>
  2060. <p>It&#8217;s not hard for a proxy reference type to provide such a conversion. For instance, the following compiles today:</p>
  2061. <pre class="brush: cpp; notranslate">std::vector&lt;bool&gt; vb{true, false, true, false};
  2062. auto it = vb.begin();
  2063. const bool &amp; val = *it;
  2064. </pre>
  2065. <p><code>*it</code> has an implicit conversion to <code>bool</code>, which binds to a <code>const bool&amp;</code>. Awesome! So the problem is solved, right? Not quite.</p>
  2066. <h2>A Panoply of Proxy Problems</h2>
  2067. <p>To better see the problems with proxy iterators, let&#8217;s look at a more interesting example: a <code>zip</code> view. When you zip two sequences together, you get a single sequence where each element is a <code>std::pair</code> of elements from the two source sequences. This can be done lazily, creating pairs on demand as the zip view is iterated:</p>
  2068. <pre class="brush: cpp; notranslate">std::vector&lt;int&gt; v1 { 1,2,3 };
  2069. std::vector&lt;int&gt; v2 { 9,8,7 };
  2070.  
  2071. auto z = view::zip( v1, v2 );
  2072. auto it = z.begin();
  2073.  
  2074. assert( *it   == std::make_pair(1,9) );
  2075. assert( *++it == std::make_pair(2,8) );
  2076. assert( *++it == std::make_pair(3,7) );
  2077. </pre>
  2078. <p>Since the zip view is generating the pairs on demand, they don&#8217;t exist anywhere in memory. <em>But the elements they refer to do!</em> See?</p>
  2079. <pre class="brush: cpp; notranslate">std::pair&lt;int&amp;,int&amp;&gt; p = *z.begin();
  2080. assert( &amp;p.first  == &amp;v1[0] );
  2081. assert( &amp;p.second == &amp;v2[0] );
  2082. </pre>
  2083. <p>The zip view is a very interesting beastie. Its reference type is <code>pair&lt;T&amp;,U&amp;&gt;</code> and its value type is <code>pair&lt;T,U&gt;</code>. This poses some very interesting challenges for the iterator concepts.</p>
  2084. <h2>1&#46; Values and References</h2>
  2085. <p>Recall that the Palo Alto TR requires <code>*it</code> to be convertible to <code>const ValueType&lt;I&gt;&amp;</code>. So we should be able to do this:</p>
  2086. <pre class="brush: cpp; notranslate">auto z = view::zip( v1, v2 );
  2087. const pair&lt;int,int&gt;&amp; val = *z.begin();
  2088. </pre>
  2089. <p>That works! As it so happens, there is a conversion from <code>std::pair&lt;T&amp;,U&amp;&gt;</code> to <code>std::pair&lt;T,U&gt;</code> &#8212; but there&#8217;s a catch: it only works if <code>T</code> and <code>U</code> are copyable! And even when they&#8217;re not, it&#8217;s clear that copying is not the behavior one would expect when using <code>*it</code> to initialize a const reference. If <code>T</code> or <code>U</code> is expensive to copy, you&#8217;re not going to get the performance or the behavior you expect, and if it&#8217;s <code>unique_ptr</code> it&#8217;s not going to compile at all. <img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f641.png" alt="🙁" class="wp-smiley" style="height: 1em; max-height: 1em;" /></p>
  2090. <p>Requiring that an iterator&#8217;s reference type be convertible to <code>const ValueType&lt;I&gt;&amp;</code> is over-constraining. But then what useful thing can we say about the relationship between these two types?</p>
  2091. <h2>2&#46; Algorithm Constraints</h2>
  2092. <p>All the algorithm signatures in the Palo Alto TR use <code>ValueType</code> in the concept checks in order to constrain the templates. For example, here&#8217;s the constrained signature of <code>for_each</code>:</p>
  2093. <pre class="brush: cpp; notranslate">template&lt;InputIterator I, Semiregular F&gt;
  2094.    requires Function&lt;F, ValueType&lt;I&gt;&gt;
  2095. F for_each(I first, I last, F f);
  2096. </pre>
  2097. <p>If you&#8217;re not familiar with C++ concepts, what lines 1 and 2 say is: <code>first</code> and <code>last</code> must satisfy the requirements of the <code>InputIterator</code> concept, <code>F</code> must be <code>Semiregular</code> (I&#8217;ll gloss over this bit), and it must be callable with one argument of the iterator&#8217;s value type.</p>
  2098. <p>Now imagine code like this:</p>
  2099. <pre class="brush: cpp; notranslate">// As before, v1 and v2 are vectors of ints:
  2100. auto z = view::zip( v1, v2 );
  2101. // Let Ref be the zip iterator's reference type:
  2102. using Ref = decltype(*z.begin());
  2103. // Use for_each to increment all the ints:
  2104. for_each( z.begin(), z.end(), [](Ref r) {
  2105.    ++r.first;
  2106.    ++r.second;
  2107. });
  2108. </pre>
  2109. <p>This seems perfectly reasonable. The lambda accepts an object of the zip view&#8217;s reference type, which is a <code>pair&lt;int&amp;,int&amp;&gt;</code>, and then it increments both first and second members. <em>But this doesn&#8217;t type-check.</em> Why?</p>
  2110. <p>Remember the concept check: <code>Function&lt;F, ValueType&lt;I&gt;&gt;</code>. The function we pass to <code>for_each</code> must be callable with an object of the iterator&#8217;s <em>value type</em>. In this case, the value type is <code>pair&lt;int,int&gt;</code>. There is no conversion from that to the type the function expects, which is <code>pair&lt;int&amp;,int&amp;&gt;</code>. Bummer.</p>
  2111. <p>If we change the lambda to take a <code>pair&lt;int,int&gt;&amp;</code>, then the concept check passes, but the template will fail to instantiate correctly. It&#8217;s easy to see why when you look at a typical <code>for_each</code> implementation:</p>
  2112. <pre class="brush: cpp; notranslate">template&lt;InputIterator I, Semiregular F&gt;
  2113. requires Function&lt;F, ValueType&lt;I&gt;&gt;
  2114. F for_each(I first, I last, F f) {
  2115.    for(; first != last; ++first)
  2116.        f(*first);
  2117.    return f;
  2118. }
  2119. </pre>
  2120. <p>The lambda is called with <code>*first</code> which has type <code>pair&lt;int&amp;,int&amp;&gt;</code>, but that doesn&#8217;t convert to <code>pair&lt;int,int&gt;&amp;</code>. Gah!!!</p>
  2121. <p>The most galling bit is that the code we wrote above &#8212; the code with the lambda that takes the reference type &#8212; works just fine if we simply delete the <code>requires Function&lt;F, ValueType&lt;I&gt;&gt;</code> constraint. Clearly something is wrong with the constraints, the concepts, or our expectations.</p>
  2122. <p>I should add that the problem is not specific to the <code>zip</code> view. Any sequence with a proxy reference type has this problem, <code>vector&lt;bool&gt;</code> included. If we just slap these constraints on the existing algorithms, some code that works today will break, and the only &#8220;fix&#8221; would be to stop using the standard algorithms. <img src="https://s.w.org/images/core/emoji/14.0.0/72x72/1f641.png" alt="🙁" class="wp-smiley" style="height: 1em; max-height: 1em;" /></p>
  2123. <h2>3&#46; Permutability of Move-Only Types</h2>
  2124. <p>Unfortunately, the problems don&#8217;t end there. The <code>sort</code> algorithm requires a sequence to be <em>permutable</em>; that is, you should be able to shuffle its elements around. And since it should support move-only types, that means that the sequence&#8217;s iterators should be <em>indirectly-movable</em>. The Palo Alto TR has this to say about it:</p>
  2125. <blockquote>
  2126. <p>The <code>IndirectlyMovable</code> and <code>IndirectlyCopyable</code> concepts describe copy and move relationships between the values of an input iterator, <code>I</code>, and an output iterator <code>Out</code>. For an output iterator <code>out</code> and an input iterator <code>in</code>, their syntactic requirements expand to:</p>
  2127. <ul>
  2128. <li><code>IndirectlyMovable</code> requires <code>*out = move(*in)</code></li>
  2129. </ul>
  2130. </blockquote>
  2131. <p>But what if <code>*in</code> returns a proxy? Then <code>move(*in)</code> is moving the proxy, not the object to which the proxy refers. In the case of sorting a zip view, we&#8217;re trying to move a (temporary) <code>pair&lt;T&amp;,U&amp;&gt;</code> into a <code>pair&lt;T&amp;,U&amp;&gt;</code>. As with issue (1), that won&#8217;t work at all for move-only types. But you would probably fail before that, at the <code>sort</code> requires clause, because of issue (2). Sheesh!</p>
  2132. <h2>Summary, For Now&#8230;</h2>
  2133. <p>Even though the Palo Alto TR lifts the over-constraining requirement that <code>ForwardIterator</code>s return real references, the proxy iterator problem remains. On the one hand, it says that proxy iterators are OK. On the other hand, some interesting proxy iterators fail to model the <code>Iterator</code> concept or satisfy the algorithm constraints, and those that do don&#8217;t have the right semantics or performance characteristics. What are our options?</p>
  2134. <ol>
  2135. <li>The <code>zip</code> view, <code>vector&lt;bool&gt;</code>, and its ilk are useful, but are not legitimate containers and ranges, and the STL can&#8217;t support them, full stop; <em>or</em></li>
  2136. <li>The iterator concepts (and probably the algorithm constraints) as specified in the Palo Alto TR need to be tweaked somehow to support proxy iterators, and some algorithm implementations probably need to change, too; <em>or</em></li>
  2137. <li>The language needs to change to better support proxy references (an idea from Sean Parent); <em>or</em></li>
  2138. <li>Something else.</li>
  2139. </ol>
  2140. <p>I really don&#8217;t like option (1); there are too many interesting forward iterators that can&#8217;t return true references, and I&#8217;m tired of doing without. I have some rudimentary ideas about option (2) that I plan to describe in my next post. Option (3) can&#8217;t be ruled out, but IANALL (I Am Not A Language Lawyer) and have no idea what would be involved. It&#8217;s clear that with C++17 shaping up, and with the Concepts Lite TR finally reaching PDTS status <em><fanfare></em>, and a range-ified, concept-ified STL in the works, the time to start making decisions about this stuff is <em>now</em>.</p>
  2141. <div style="display:none">
  2142. <pre class="brush: cpp; title: ; notranslate">&quot;\e&quot;</pre>
  2143. </div>
  2144. ]]></content:encoded>
  2145. <wfw:commentRss>https://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/feed/</wfw:commentRss>
  2146. <slash:comments>31</slash:comments>
  2147. <post-id xmlns="com-wordpress:feed-additions:1">826</post-id> </item>
  2148. </channel>
  2149. </rss>
  2150.  

If you would like to create a banner that links to this page (i.e. this validation result), do the following:

  1. Download the "valid RSS" banner.

  2. Upload the image to your own server. (This step is important. Please do not link directly to the image on this server.)

  3. Add this HTML to your page (change the image src attribute if necessary):

If you would like to create a text link instead, here is the URL you can use:

http://www.feedvalidator.org/check.cgi?url=http%3A//ericniebler.com/feed/

Copyright © 2002-9 Sam Ruby, Mark Pilgrim, Joseph Walton, and Phil Ringnalda