Merge PR-2103 from sverker/ets-iteration-doc/OTP-15545

Clarify ETS docs about table iterations

1 files changed, 87 insertions, 34 deletions

diff --git a/lib/stdlib/doc/src/ets.xml b/lib/stdlib/doc/src/ets.xml
index 70d1aaa74d..ccccf7de88 100644
--- a/lib/stdlib/doc/src/ets.xml
+++ b/lib/stdlib/doc/src/ets.xml
@@ -138,23 +138,56 @@
        operation. In database terms the isolation level can be seen as
        "serializable", as if all isolated operations are carried out serially,
        one after the other in a strict order.</p>
+  </section>
 
-      <p>No other support is available within this module that would guarantee
-       consistency between objects. However, function
-       <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
-       can be used to guarantee that a sequence of
-       <seealso marker="#first/1"><c>first/1</c></seealso> and
-       <seealso marker="#next/2"><c>next/2</c></seealso> calls traverse the
-       table without errors and that each existing object in the table is
-       visited exactly once, even if another (or the same) process
-       simultaneously deletes or inserts objects into the table.
-       Nothing else is guaranteed; in particular objects that are inserted
-       or deleted during such a traversal can be visited once or not at all.
-       Functions that internally traverse over a table, like
-       <seealso marker="#select/1"><c>select</c></seealso> and
-       <seealso marker="#match/1"><c>match</c></seealso>,
-       give the same guarantee as
-       <seealso marker="#safe_fixtable/2"><c>safe_fixtable</c></seealso>.</p>
+  <section><marker id="traversal"></marker>
+    <title>Table traversal</title>
+    <p>There are different ways to traverse through the objects of a table.</p>
+    <list type="bulleted">
+      <item><p><em>Single-step</em> traversal one key at at time, using
+	<seealso marker="#first/1"><c>first/1</c></seealso>,
+	<seealso marker="#next/2"><c>next/2</c></seealso>,
+	<seealso marker="#last/1"><c>last/1</c></seealso> and
+	<seealso marker="#prev/2"><c>prev/2</c></seealso>.</p>
+      </item>
+      <item><p>Search with simple <em>match patterns</em>, using
+	<seealso marker="#match/1"><c>match/1/2/3</c></seealso>,
+	<seealso marker="#match_delete/2"><c>match_delete/2</c></seealso> and
+	<seealso marker="#match_object/1"><c>match_object/1/2/3</c></seealso>.</p>
+      </item>
+      <item><p>Search with more powerful <em>match specifications</em>, using
+	<seealso marker="#select/1"><c>select/1/2/3</c></seealso>,
+	<seealso marker="#select_count/2"><c>select_count/2</c></seealso>,
+	<seealso marker="#select_delete/2"><c>select_delete/2</c></seealso>,
+	<seealso marker="#select_replace/2"><c>select_replace/2</c></seealso> and
+	<seealso marker="#select_reverse/1"><c>select_reverse/1/2/3</c></seealso>.</p>
+      </item>
+      <item><p><em>Table conversions</em>, using
+	<seealso marker="#tab2file/2"><c>tab2file/2/3</c></seealso> and
+        <seealso marker="#tab2list/1"><c>tab2list/1</c></seealso>.</p>
+      </item>
+    </list>
+    <p>None of these ways of table traversal will guarantee a consistent table snapshot
+    if the table is also updated during the traversal. Moreover, traversals not
+    done in a <em>safe</em> way, on tables where keys are inserted or deleted
+    during the traversal, may yield the following undesired effects:</p>
+    <list type="bulleted">
+      <item><p>Any key may be missed.</p></item>
+      <item><p>Any key may be found more than once.</p></item>
+      <item><p>The traversal may fail with <c>badarg</c> exception if keys are deleted.</p>
+      </item>
+    </list>
+    <p>A table traversal is <em>safe</em> if either</p>
+    <list type="bulleted">
+      <item><p>the table is of type <c>ordered_set</c>.</p>
+      </item>
+      <item><p>the entire table traversal is done within one ETS function
+        call.</p>
+      </item>
+      <item><p>function <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+        is used to keep the table fixated during the entire traversal.</p>
+      </item>
+    </list>
   </section>
 
   <section>
@@ -871,6 +904,9 @@ ets:is_compiled_ms(Broken).</code>
           <seealso marker="#first/1"><c>first/1</c></seealso> and
           <seealso marker="#next/2"><c>next/2</c></seealso>.</p>
         <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+	<p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+	  to guarantee <seealso marker="#traversal">safe traversal</seealso>
+	  for subsequent calls to <seealso marker="#match/1"><c>match/1</c></seealso>.</p>
       </desc>
     </func>
 
@@ -936,6 +972,10 @@ ets:is_compiled_ms(Broken).</code>
           <seealso marker="#first/1"><c>first/1</c></seealso> and
           <seealso marker="#next/2"><c>next/2</c></seealso>.</p>
         <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+	<p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+	  to guarantee <seealso marker="#traversal">safe traversal</seealso>
+	  for subsequent calls to <seealso marker="#match_object/1">
+	  <c>match_object/1</c></seealso>.</p>
       </desc>
     </func>
 
@@ -1192,12 +1232,13 @@ ets:select(Table, MatchSpec),</code>
         <p>To find the first key in the table, use
           <seealso marker="#first/1"><c>first/1</c></seealso>.</p>
         <p>Unless a table of type <c>set</c>, <c>bag</c>, or
-          <c>duplicate_bag</c> is protected using
+          <c>duplicate_bag</c> is fixated using
           <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>,
-          a traversal can fail if
-          concurrent updates are made to the table. For table
-          type <c>ordered_set</c>, the function returns the next key in
-          order, even if the object does no longer exist.</p>
+          a call to <c>next/2</c> will fail if <c><anno>Key1</anno></c> no longer
+	  exists in the table. For table type <c>ordered_set</c>, the function
+	  always returns the next key after <c><anno>Key1</anno></c> in term
+	  order, regardless whether <c><anno>Key1</anno></c> ever existed in the
+	  table.</p>
       </desc>
     </func>
 
@@ -1212,7 +1253,7 @@ ets:select(Table, MatchSpec),</code>
           table types, the function is synonymous to
           <seealso marker="#next/2"><c>next/2</c></seealso>.
           If no previous key exists, <c>'$end_of_table'</c> is returned.</p>
-        <p>To find the last key in the table, use
+        <p>To find the last key in an <c>ordered_set</c> table, use
           <seealso marker="#last/1"><c>last/1</c></seealso>.</p>
       </desc>
     </func>
@@ -1287,7 +1328,16 @@ ets:select(ets:repair_continuation(Broken,MS)).</code>
       <fsummary>Fix an ETS table for safe traversal.</fsummary>
       <desc>
         <p>Fixes a table of type <c>set</c>, <c>bag</c>, or
-          <c>duplicate_bag</c> for safe traversal.</p>
+        <c>duplicate_bag</c> for <seealso marker="#traversal">
+	safe traversal</seealso> using
+	<seealso marker="#first/1"><c>first/1</c></seealso> &amp;
+	<seealso marker="#next/2"><c>next/2</c></seealso>,
+	<seealso marker="#match/3"><c>match/3</c></seealso> &amp;
+	<seealso marker="#match/1"><c>match/1</c></seealso>,
+	<seealso marker="#match_object/3"><c>match_object/3</c></seealso> &amp;
+	<seealso marker="#match_object/1"><c>match_object/1</c></seealso>, or
+	<seealso marker="#select/3"><c>select/3</c></seealso> &amp;
+	<seealso marker="#select/1"><c>select/1</c></seealso>.</p>
         <p>A process fixes a table by calling
           <c>safe_fixtable(<anno>Tab</anno>, true)</c>. The table remains
           fixed until the process releases it by calling
@@ -1300,11 +1350,11 @@ ets:select(ets:repair_continuation(Broken,MS)).</code>
         <p>When a table is fixed, a sequence of
           <seealso marker="#first/1"><c>first/1</c></seealso> and
           <seealso marker="#next/2"><c>next/2</c></seealso> calls are
-          guaranteed to succeed, and each object in
-          the table is returned only once, even if objects
-          are removed or inserted during the traversal. The keys for new
-          objects inserted during the traversal <em>can</em> be returned by
-          <c>next/2</c> (it depends on the internal ordering of the keys).</p>
+          guaranteed to succeed even if keys are removed during the
+	  traversal. The keys for objects inserted or deleted during a
+	  traversal may or may not be returned by <c>next/2</c> depending on
+	  the ordering of keys within the table and if the key exists at the time
+	  <c>next/2</c> is called.</p>
         <p><em>Example:</em></p>
         <code type="none">
 clean_all_with_value(Tab,X) ->
@@ -1322,7 +1372,7 @@ clean_all_with_value(Tab,X,Key) ->
             true
     end,
     clean_all_with_value(Tab,X,ets:next(Tab,Key)).</code>
-        <p>Notice that no deleted objects are removed from a
+        <p>Notice that deleted objects are not freed from a
           fixed table until it has been released. If a process fixes a
           table but never releases it, the memory used by the deleted
           objects is never freed. The performance of operations on
@@ -1332,9 +1382,9 @@ clean_all_with_value(Tab,X,Key) ->
           <c>info(Tab, safe_fixed_monotonic_time)</c></seealso>. A system with
           many processes fixing tables can need a monitor that sends alarms
           when tables have been fixed for too long.</p>
-        <p>Notice that for table type <c>ordered_set</c>,
-          <c>safe_fixtable/2</c> is not necessary, as calls to
-          <c>first/1</c> and <c>next/2</c> always succeed.</p>
+        <p>Notice that <c>safe_fixtable/2</c> is not necessary for table type
+	<c>ordered_set</c> and for traversals done by a single ETS function call,
+	like <seealso marker="#select/2"><c>select/2</c></seealso>.</p>
       </desc>
     </func>
 
@@ -1462,7 +1512,10 @@ is_integer(X), is_integer(Y), X + Y < 4711]]></code>
           table, which is still faster than traversing the table object by
           object using <seealso marker="#first/1"><c>first/1</c></seealso>
           and <seealso marker="#next/2"><c>next/2</c></seealso>.</p>
-        <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+          <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+	  <p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+	  to guarantee <seealso marker="#traversal">safe traversal</seealso>
+	  for subsequent calls to <seealso marker="#select/1"><c>select/1</c></seealso>.</p>
       </desc>
     </func>
 
@@ -1519,7 +1572,7 @@ is_integer(X), is_integer(Y), X + Y < 4711]]></code>
           the match specification result.</p>
 	<p>The match-and-replace operation for each individual object is guaranteed to be
 	  <seealso marker="#concurrency">atomic and isolated</seealso>. The
-	  <c>select_replace</c> table iteration as a whole, like all other select functions,
+	  <c>select_replace</c> table traversal as a whole, like all other select functions,
 	  does not give such guarantees.</p>
 	<p>The match specifiction must be guaranteed to <em>retain the key</em>
 	  of any matched object. If not, <c>select_replace</c> will fail with <c>badarg</c>