From d945d6f1c71d5442a25e4be60f84fc49ae8b6b4e Mon Sep 17 00:00:00 2001
From: Lukas Larsson <lukas@erlang.org>
Date: Tue, 19 Sep 2017 12:01:09 +0200
Subject: stdlib: Introduce maps iterator API

---
 lib/stdlib/src/maps.erl | 76 ++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 62 insertions(+), 14 deletions(-)

(limited to 'lib/stdlib')

diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 5dafdb282a..7ed32a3988 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -23,7 +23,8 @@
 -export([get/3, filter/2,fold/3,
          map/2, size/1,
          update_with/3, update_with/4,
-         without/2, with/2]).
+         without/2, with/2,
+         iterator/1, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -31,6 +32,10 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
+-opaque iterator() :: [{term(), term()}].
+
+-export_type([iterator/0]).
+
 %% Shadowed by erl_bif_types: maps:get/2
 -spec get(Key,Map) -> Value when
     Key :: term(),
@@ -200,10 +205,22 @@ get(Key,Map,Default) ->
       Map2 :: map().
 
 filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
-    maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+    maps:from_list(filter_1(Pred, iterator(Map)));
 filter(Pred,Map) ->
     erlang:error(error_type(Map),[Pred,Map]).
 
+filter_1(Pred, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            case Pred(K,V) of
+                true ->
+                    [{K,V} | filter_1(Pred, NextIter)];
+                false ->
+                    filter_1(Pred, NextIter)
+            end;
+        none ->
+            []
+    end.
 
 -spec fold(Fun,Init,Map) -> Acc when
     Fun :: fun((K, V, AccIn) -> AccOut),
@@ -216,10 +233,18 @@ filter(Pred,Map) ->
     V :: term().
 
 fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
-    lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+    fold_1(Fun, Init, iterator(Map));
 fold(Fun,Init,Map) ->
     erlang:error(error_type(Map),[Fun,Init,Map]).
 
+fold_1(Fun, Acc, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            fold_1(Fun, Fun(K,V,Acc), NextIter);
+        none ->
+            Acc
+    end.
+
 -spec map(Fun,Map1) -> Map2 when
     Fun :: fun((K, V1) -> V2),
     Map1 :: map(),
@@ -229,10 +254,17 @@ fold(Fun,Init,Map) ->
     V2 :: term().
 
 map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
-    maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+    maps:from_list(map_1(Fun, iterator(Map)));
 map(Fun,Map) ->
     erlang:error(error_type(Map),[Fun,Map]).
 
+map_1(Fun, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            [{K, Fun(K, V)} | map_1(Fun, NextIter)];
+        none ->
+            []
+    end.
 
 -spec size(Map) -> non_neg_integer() when
     Map :: map().
@@ -242,6 +274,23 @@ size(Map) when is_map(Map) ->
 size(Val) ->
     erlang:error({badmap,Val},[Val]).
 
+-spec iterator(Map) -> Iterator when
+      Map :: map(),
+      Iterator :: iterator().
+
+iterator(Map) when is_map(Map) ->
+    maps:to_list(Map);
+iterator(M) ->
+    erlang:error(error_type(M),[M]).
+
+-spec next(Iterator) -> {K,V,NextIterator} | 'none' when
+      Iterator :: iterator(),
+      K :: term(),
+      V :: term(),
+      NextIterator :: iterator().
+next([]) -> none;
+next([{K, V} | I]) ->
+    {K, V, I}.
 
 -spec without(Ks,Map1) -> Map2 when
     Ks :: [K],
@@ -250,11 +299,10 @@ size(Val) ->
     K :: term().
 
 without(Ks,M) when is_list(Ks), is_map(M) ->
-    lists:foldl(fun(K, M1) -> ?MODULE:remove(K, M1) end, M, Ks);
+    lists:foldl(fun(K, M1) -> maps:remove(K, M1) end, M, Ks);
 without(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
-
 -spec with(Ks, Map1) -> Map2 when
     Ks :: [K],
     Map1 :: map(),
@@ -263,14 +311,14 @@ without(Ks,M) ->
 
 with(Ks,Map1) when is_list(Ks), is_map(Map1) ->
     Fun = fun(K, List) ->
-      case ?MODULE:find(K, Map1) of
-          {ok, V} ->
-              [{K, V} | List];
-          error ->
-              List
-      end
-    end,
-    ?MODULE:from_list(lists:foldl(Fun, [], Ks));
+                  case maps:find(K, Map1) of
+                      {ok, V} ->
+                          [{K, V} | List];
+                      error ->
+                          List
+                  end
+          end,
+    maps:from_list(lists:foldl(Fun, [], Ks));
 with(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
-- 
cgit v1.2.3


From 513a322941d208d9dcdc4c39db2966ae4c707fe7 Mon Sep 17 00:00:00 2001
From: Lukas Larsson <lukas@erlang.org>
Date: Tue, 19 Sep 2017 14:37:59 +0200
Subject: erts: Implement map iterator using a stack

This version does not work great as the subtrees
created are not proper hash maps. Also it is not
all that performant as the extra allocations to
keep the stack there is expensive.
---
 lib/stdlib/src/maps.erl | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

(limited to 'lib/stdlib')

diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 7ed32a3988..0da12cf8e2 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -32,7 +32,7 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
--opaque iterator() :: [{term(), term()}].
+-opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]].
 
 -export_type([iterator/0]).
 
@@ -279,7 +279,10 @@ size(Val) ->
       Iterator :: iterator().
 
 iterator(Map) when is_map(Map) ->
-    maps:to_list(Map);
+    case maps:size(Map) < 42 of
+        true -> maps:to_list(Map);
+        false -> [[1 | Map]]
+    end;
 iterator(M) ->
     erlang:error(error_type(M),[M]).
 
@@ -289,6 +292,12 @@ iterator(M) ->
       V :: term(),
       NextIterator :: iterator().
 next([]) -> none;
+next([[Index | Map] | St]) ->
+    case erts_internal:map_get_index(Index, Map) of
+        SubMap when is_map(SubMap) -> next([[1 | SubMap], [Index+1|Map] | St]);
+        [K|V] -> {K,V,[[Index+1 | Map] | St]};
+        none -> next(St)
+    end;
 next([{K, V} | I]) ->
     {K, V, I}.
 
-- 
cgit v1.2.3


From 0149a73d15df1f80cb46752ec3829f48c38dd230 Mon Sep 17 00:00:00 2001
From: Lukas Larsson <lukas@erlang.org>
Date: Thu, 21 Sep 2017 09:20:30 +0200
Subject: erts: Implement maps path iterator

---
 lib/stdlib/doc/src/maps.xml    | 138 ++++++++++++++++++++++++++++++++++++++---
 lib/stdlib/src/maps.erl        |  91 +++++++++++++++++----------
 lib/stdlib/test/maps_SUITE.erl |  63 +++++++++++++++++++
 3 files changed, 251 insertions(+), 41 deletions(-)

(limited to 'lib/stdlib')

diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index 8c7270816b..a3afbf8e7f 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -33,16 +33,32 @@
     <p>This module contains functions for maps processing.</p>
   </description>
 
+  <datatypes>
+    <datatype>
+      <name name="iterator"/>
+      <desc>
+        <p>An iterator representing the key value associations in a map.</p>
+        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>
+        and <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>.</p>
+        <p>Consumed by <seealso marker="#next-1"><c>maps:next/1</c></seealso>,
+          <seealso marker="#filter-2"><c>maps:filter/2</c></seealso>,
+          <seealso marker="#fold-3"><c>maps:fold/3</c></seealso> and
+          <seealso marker="#map-2"><c>maps:map/2</c></seealso>.</p>
+      </desc>
+    </datatype>
+  </datatypes>
+
   <funcs>
     <func>
       <name name="filter" arity="2"/>
       <fsummary>Select pairs that satisfy a predicate.</fsummary>
       <desc>
-        <p>Returns a map <c><anno>Map2</anno></c> for which predicate
-          <c><anno>Pred</anno></c> holds true in <c><anno>Map1</anno></c>.</p>
+        <p>Returns a map <c><anno>Map</anno></c> for which predicate
+          <c><anno>Pred</anno></c> holds true in <c><anno>MapOrIter</anno></c>.</p>
         <p>The call fails with a <c>{badmap,Map}</c> exception if
-          <c><anno>Map1</anno></c> is not a map, or with <c>badarg</c> if
-          <c><anno>Pred</anno></c> is not a function of arity 2.</p>
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Pred</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > M = #{a => 2, b => 3, c=> 4, "a" => 1, "b" => 2, "c" => 4},
@@ -76,12 +92,16 @@
       <fsummary></fsummary>
       <desc>
         <p>Calls <c>F(K, V, AccIn)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V</anno></c> association in <c><anno>Map</anno></c> in
+          <c><anno>V</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/3</c> must return a new
           accumulator, which is passed to the next successive call.
           This function returns the final value of the accumulator. The initial
           accumulator value <c><anno>Init</anno></c> is returned if the map is
           empty.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 3.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V,AccIn) when is_list(K) -> AccIn + V end,
@@ -168,6 +188,75 @@ false</code>
       </desc>
     </func>
 
+    <func>
+      <name name="iterator" arity="1"/>
+      <fsummary>Create a map iterator.</fsummary>
+      <desc>
+        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
+          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
+          to traverse the keys and values in a map. This call is equivalent
+          to calling <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>
+          with an empty map as the options.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>Map</anno></c> is not a map.</p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> M = #{ a => 1, b => 2 }.
+#{a => 1,b => 2}
+> I = maps:iterator(M).
+[{a,1},{b,2}]
+> {K1, V1, I2} = maps:next(I).
+{a,1,[{b,2}]}
+> {K2, V2, I3} = maps:next(I2).
+{b,2,[]}
+> maps:next(I3).
+none</code>
+      </desc>
+    </func>
+
+    <func>
+      <name name="iterator" arity="2"/>
+      <fsummary>Create a map iterator.</fsummary>
+      <desc>
+        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
+          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
+          to traverse the keys and values in a map. The iterator will behave
+          according to the given <c><anno>Opts</anno></c>.</p>
+        <taglist>
+          <tag>optimize</tag>
+          <item>
+            Configures whether the iterator should be optimized for <c>speed</c>
+            or for <c>memory</c> consumption. Default is <c>speed</c>.
+          </item>
+          <tag>ordered</tag>
+          <item>
+            Configures whether the iterator should return the key value
+            associations ordered on the keys according to erlang term order
+            or not. The default is <c>false</c>.
+          </item>
+        </taglist>
+        <p>Both options can be configured at the same time.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>Map</anno></c> is not a map.</p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> M = maps:from_list([{I,I} || I &lt;- lists:seq(1,50)]).
+#{45 => 45,6 => 6,2 => 2,49 => 49,41 => 41,33 => 33,42 => 42,
+  43 => 43,10 => 10,9 => 9,19 => 19,14 => 14,5 => 5,18 => 18,
+  31 => 31,22 => 22,29 => 29,21 => 21,27 => 27,24 => 24,
+  47 => 47,40 => 40,30 => 30,23 => 23,28 => 28,46 => 46,
+  16 => 16,38 => 38,4 => 4,...}
+> MemoryIter = maps:iterator(M, #{ optimize => memory }), ok.
+ok
+> {K1, V1, _} = maps:next(MemoryIter), {K1, V1}.
+{46,46}
+> OrderedIter = maps:iterator(M, #{ ordered => true, optimize => memory }), ok.
+ok
+> {K2, V2, _} = maps:next(OrderedIter), {K2, V2}.
+{1,1}</code>
+      </desc>
+    </func>
+
     <func>
       <name name="keys" arity="1"/>
       <fsummary></fsummary>
@@ -188,12 +277,16 @@ false</code>
       <name name="map" arity="2"/>
       <fsummary></fsummary>
       <desc>
-        <p>Produces a new map <c><anno>Map2</anno></c> by calling function
+        <p>Produces a new map <c><anno>Map</anno></c> by calling function
           <c>fun F(K, V1)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V1</anno></c> association in <c><anno>Map1</anno></c> in
+          <c><anno>V1</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/2</c> must return value
           <c><anno>V2</anno></c> to be associated with key <c><anno>K</anno></c>
-          for the new map <c><anno>Map2</anno></c>.</p>
+          for the new map <c><anno>Map</anno></c>.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V1) when is_list(K) -> V1*2 end,
@@ -233,6 +326,35 @@ false</code>
       </desc>
     </func>
 
+    <func>
+      <name name="next" arity="1"/>
+      <fsummary>Get the next key and value from an iterator.</fsummary>
+      <desc>
+        <p>Returns the next key-value association in
+          <c><anno>Iterator</anno></c> and a new iterator for the
+          remaining associations in the iterator.
+        </p>
+        <p>
+          If there are no more associations in the iterator,
+          <c>none</c> is returned.
+        </p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> Map = #{a => 1, b => 2, c => 3}.
+#{a => 1,b => 2,c => 3}
+> Iter = maps:iterator(Map).
+[{a,1},{b,2},{c,3}]
+> {_, _, Iter1} = maps:next(Iter).
+{a,1,[{b,2},{c,3}]}
+> {_, _, Iter2} = maps:next(Iter1).
+{b,2,[{c,3}]}
+> {_, _, Iter3} = maps:next(Iter2).
+{c,3,[]}
+> maps:next(Iter3).
+none</code>
+      </desc>
+    </func>
+
     <func>
       <name name="put" arity="3"/>
       <fsummary></fsummary>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 0da12cf8e2..2f2dd41979 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -24,7 +24,7 @@
          map/2, size/1,
          update_with/3, update_with/4,
          without/2, with/2,
-         iterator/1, next/1]).
+         iterator/1, iterator/2, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -32,10 +32,13 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
--opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]].
+-opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
+                    | list({term(), term()}).
 
 -export_type([iterator/0]).
 
+-define(IS_ITERATOR(I), (is_list(I) orelse (is_map(element(2,I) andalso (is_list(element(1,I) orelse is_integer(element(1,I)))))))).
+
 %% Shadowed by erl_bif_types: maps:get/2
 -spec get(Key,Map) -> Value when
     Key :: term(),
@@ -44,7 +47,6 @@
 
 get(_,_) -> erlang:nif_error(undef).
 
-
 -spec find(Key,Map) -> {ok, Value} | error when
     Key :: term(),
     Map :: map(),
@@ -197,15 +199,17 @@ get(Key,Map,Default) ->
     erlang:error({badmap,Map},[Key,Map,Default]).
 
 
--spec filter(Pred,Map1) -> Map2 when
+-spec filter(Pred,MapOrIter) -> Map when
       Pred :: fun((Key, Value) -> boolean()),
       Key  :: term(),
       Value :: term(),
-      Map1 :: map(),
-      Map2 :: map().
+      MapOrIter :: map() | iterator(),
+      Map :: map().
 
 filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
-    maps:from_list(filter_1(Pred, iterator(Map)));
+    maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
+    maps:from_list(filter_1(Pred, Iterator));
 filter(Pred,Map) ->
     erlang:error(error_type(Map),[Pred,Map]).
 
@@ -222,18 +226,20 @@ filter_1(Pred, Iter) ->
             []
     end.
 
--spec fold(Fun,Init,Map) -> Acc when
+-spec fold(Fun,Init,MapOrIter) -> Acc when
     Fun :: fun((K, V, AccIn) -> AccOut),
     Init :: term(),
     Acc :: term(),
     AccIn :: term(),
     AccOut :: term(),
-    Map :: map(),
+    MapOrIter :: map() | iterator(),
     K :: term(),
     V :: term().
 
 fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
-    fold_1(Fun, Init, iterator(Map));
+    lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
+    fold_1(Fun,Init,Iterator);
 fold(Fun,Init,Map) ->
     erlang:error(error_type(Map),[Fun,Init,Map]).
 
@@ -245,16 +251,18 @@ fold_1(Fun, Acc, Iter) ->
             Acc
     end.
 
--spec map(Fun,Map1) -> Map2 when
+-spec map(Fun,MapOrIter) -> Map when
     Fun :: fun((K, V1) -> V2),
-    Map1 :: map(),
-    Map2 :: map(),
+    MapOrIter :: map() | iterator(),
+    Map :: map(),
     K :: term(),
     V1 :: term(),
     V2 :: term().
 
 map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
-    maps:from_list(map_1(Fun, iterator(Map)));
+    maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
+    maps:from_list(map_1(Fun, Iterator));
 map(Fun,Map) ->
     erlang:error(error_type(Map),[Fun,Map]).
 
@@ -278,28 +286,45 @@ size(Val) ->
       Map :: map(),
       Iterator :: iterator().
 
-iterator(Map) when is_map(Map) ->
-    case maps:size(Map) < 42 of
-        true -> maps:to_list(Map);
-        false -> [[1 | Map]]
+iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) -> erlang:error({badmap, M}, [M]).
+
+-spec iterator(Map, Opts) -> Iterator when
+      Map :: map(),
+      Opts :: #{ ordered => boolean(), optimize => speed | memory },
+      Iterator :: iterator().
+iterator(M, Opts) when is_map(M), is_map(Opts) ->
+    case maps:merge(default_iterator_opts(), Opts) of
+        #{ ordered := true, optimize := speed} -> lists:sort(maps:to_list(M));
+        #{ ordered := false, optimize := speed} -> maps:to_list(M);
+        #{ ordered := true, optimize := memory} -> {lists:sort(maps:keys(M)), M};
+        #{ ordered := false, optimize := memory} -> {0, M}
     end;
-iterator(M) ->
-    erlang:error(error_type(M),[M]).
+iterator(M, Opts) when is_map(M) ->
+    erlang:error({badmap, M}, [M, Opts]);
+iterator(M, Opts) ->
+    erlang:error(error_type(M), [M, Opts]).
+
+default_iterator_opts() ->
+    #{ ordered => false, optimize => speed }.
 
--spec next(Iterator) -> {K,V,NextIterator} | 'none' when
+-spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
       Iterator :: iterator(),
-      K :: term(),
-      V :: term(),
+      Key :: term(),
+      Value :: term(),
       NextIterator :: iterator().
-next([]) -> none;
-next([[Index | Map] | St]) ->
-    case erts_internal:map_get_index(Index, Map) of
-        SubMap when is_map(SubMap) -> next([[1 | SubMap], [Index+1|Map] | St]);
-        [K|V] -> {K,V,[[Index+1 | Map] | St]};
-        none -> next(St)
-    end;
-next([{K, V} | I]) ->
-    {K, V, I}.
+next([{K, V} | T]) ->
+    {K, V, T};
+next([]) ->
+    none;
+next({I, M}) when is_map(M), is_integer(I) orelse is_atom(I) ->
+    erts_internal:map_next(I, M);
+next({[K | T], M}) when is_map(M) ->
+    {K, maps:get(K, M), {T, M}};
+next({[], M}) when is_map(M) ->
+    none;
+next(Iter) ->
+    erlang:error(badarg, [Iter]).
 
 -spec without(Ks,Map1) -> Map2 when
     Ks :: [K],
@@ -332,5 +357,5 @@ with(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
 
-error_type(M) when is_map(M) -> badarg;
+error_type(M) when is_map(M); ?IS_ITERATOR(M) -> badarg;
 error_type(V) -> {badmap, V}.
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 42e669a799..0021dd0657 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,6 +30,7 @@
 -export([t_update_with_3/1, t_update_with_4/1,
          t_get_3/1, t_filter_2/1,
          t_fold_3/1,t_map_2/1,t_size_1/1,
+         t_iterator_1/1, t_iterator_2/1,
          t_with_2/1,t_without_2/1]).
 
 %%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -47,6 +48,7 @@ all() ->
     [t_update_with_3,t_update_with_4,
      t_get_3,t_filter_2,
      t_fold_3,t_map_2,t_size_1,
+     t_iterator_1, t_iterator_2,
      t_with_2,t_without_2].
 
 t_update_with_3(Config) when is_list(Config) ->
@@ -127,6 +129,8 @@ t_filter_2(Config) when is_list(Config) ->
     Pred2 = fun(K,V) -> is_list(K) andalso (V rem 2) =:= 0 end,
     #{a := 2,c := 4} = maps:filter(Pred1,M),
     #{"b" := 2,"c" := 4} = maps:filter(Pred2,M),
+    #{a := 2,c := 4} = maps:filter(Pred1,maps:iterator(M)),
+    #{"b" := 2,"c" := 4} = maps:filter(Pred2,maps:iterator(M)),
     %% error case
     ?badmap(a,filter,[_,a]) = (catch maps:filter(fun(_,_) -> ok end,id(a))),
     ?badarg(filter,[<<>>,#{}]) = (catch maps:filter(id(<<>>),#{})),
@@ -139,6 +143,8 @@ t_fold_3(Config) when is_list(Config) ->
     Tot0 = lists:sum(Vs),
     Tot1 = maps:fold(fun({k,_},V,A) -> A + V end, 0, M0),
     true = Tot0 =:= Tot1,
+    Tot2 = maps:fold(fun({k,_},V,A) -> A + V end, 0, maps:iterator(M0)),
+    true = Tot0 =:= Tot2,
 
     %% error case
     ?badmap(a,fold,[_,0,a]) = (catch maps:fold(fun(_,_,_) -> ok end,0,id(a))),
@@ -151,12 +157,69 @@ t_map_2(Config) when is_list(Config) ->
     #{ {k,1} := 1, {k,200} := 200} = M0,
     M1 = maps:map(fun({k,_},V) -> V + 42 end, M0),
     #{ {k,1} := 43, {k,200} := 242} = M1,
+    M2 = maps:map(fun({k,_},V) -> V + 42 end, maps:iterator(M0)),
+    #{ {k,1} := 43, {k,200} := 242} = M2,
 
     %% error case
     ?badmap(a,map,[_,a]) = (catch maps:map(fun(_,_) -> ok end, id(a))),
     ?badarg(map,[<<>>,#{}]) = (catch maps:map(id(<<>>),#{})),
     ok.
 
+t_iterator_1(Config) when is_list(Config) ->
+
+    %% Small map test
+    M0 = #{ a => 1, b => 2 },
+    I0 = maps:iterator(M0),
+    {K1,V1,I1} = maps:next(I0),
+    {K2,V2,I2} = maps:next(I1),
+    none = maps:next(I2),
+
+    KVList = lists:sort([{K1,V1},{K2,V2}]),
+    KVList = lists:sort(maps:to_list(M0)),
+
+    %% Large map test
+
+    Vs = lists:seq(1,200),
+    M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+    KVList2 = lists:sort(iter_kv(maps:iterator(M2))),
+    KVList2 = lists:sort(maps:to_list(M2)),
+    ok.
+
+t_iterator_2(Config) when is_list(Config) ->
+
+    Vs = lists:seq(1,200),
+    Maps = [#{ a => 1, b => 2 }, maps:from_list([{{k,I},I}||I<-Vs])],
+    Optimize = [speed, memory],
+    Ordered = [true, false],
+
+    [test_iterator(Map, Opt, Ord) || Map <- Maps,
+                                     Opt <- Optimize,
+                                     Ord <- Ordered],
+
+    ok.
+
+test_iterator(Map, Opt, Ord) ->
+    Opts = #{ optimize => Opt, ordered => Ord },
+    test_iterator_1(maps:iterator(Map, Opts), Map, Opts).
+
+test_iterator_1(Iter, OrigMap, Opts) ->
+    erlang:display(Opts),
+    KVs = iter_kv(Iter),
+    case Opts of
+        #{ ordered := true } ->
+            KVs = lists:sort(maps:to_list(OrigMap));
+        #{ ordered := false } ->
+            OrderedKVs = lists:sort(KVs),
+            OrderedKVs = lists:sort(maps:to_list(OrigMap))
+    end.
+
+iter_kv(I) ->
+    case maps:next(I) of
+        none ->
+            [];
+        {K,V,NI} ->
+            [{K,V} | iter_kv(NI)]
+    end.
 
 t_size_1(Config) when is_list(Config) ->
       0 = maps:size(#{}),
-- 
cgit v1.2.3


From a1c796e7f6b86b4b506492ae6354382c565278d1 Mon Sep 17 00:00:00 2001
From: Lukas Larsson <lukas@erlang.org>
Date: Thu, 12 Oct 2017 16:00:50 +0200
Subject: erts: Implement batching maps:iterator

This iterator implementation fetches multiple elements to
iterate over in one call to erts_internal:maps_next instead
of one at a time. This means that the memory usage will go
up for the iterator as we are buffering elements, but the
usage is still bounded.

In this implementation the max memory usage is 1000 words.

Using this approach makes the iterator as fast as using
maps:to_list, so maps:iterator/2 has been removed.
---
 lib/stdlib/doc/src/maps.xml    | 52 +++--------------------------------
 lib/stdlib/src/maps.erl        | 61 ++++++++++++++++--------------------------
 lib/stdlib/test/maps_SUITE.erl | 39 +++++++--------------------
 3 files changed, 36 insertions(+), 116 deletions(-)

(limited to 'lib/stdlib')

diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index a3afbf8e7f..987d92989d 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -38,8 +38,7 @@
       <name name="iterator"/>
       <desc>
         <p>An iterator representing the key value associations in a map.</p>
-        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>
-        and <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>.</p>
+        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>.</p>
         <p>Consumed by <seealso marker="#next-1"><c>maps:next/1</c></seealso>,
           <seealso marker="#filter-2"><c>maps:filter/2</c></seealso>,
           <seealso marker="#fold-3"><c>maps:fold/3</c></seealso> and
@@ -194,9 +193,9 @@ false</code>
       <desc>
         <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
           be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
-          to traverse the keys and values in a map. This call is equivalent
-          to calling <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>
-          with an empty map as the options.</p>
+          to traverse the key-value associations in a map. When iterating
+          over a map, the memory usage is guaranteed to be bounded no matter
+          the size of the map.</p>
         <p>The call fails with a <c>{badmap,Map}</c> exception if
           <c><anno>Map</anno></c> is not a map.</p>
         <p><em>Example:</em></p>
@@ -214,49 +213,6 @@ none</code>
       </desc>
     </func>
 
-    <func>
-      <name name="iterator" arity="2"/>
-      <fsummary>Create a map iterator.</fsummary>
-      <desc>
-        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
-          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
-          to traverse the keys and values in a map. The iterator will behave
-          according to the given <c><anno>Opts</anno></c>.</p>
-        <taglist>
-          <tag>optimize</tag>
-          <item>
-            Configures whether the iterator should be optimized for <c>speed</c>
-            or for <c>memory</c> consumption. Default is <c>speed</c>.
-          </item>
-          <tag>ordered</tag>
-          <item>
-            Configures whether the iterator should return the key value
-            associations ordered on the keys according to erlang term order
-            or not. The default is <c>false</c>.
-          </item>
-        </taglist>
-        <p>Both options can be configured at the same time.</p>
-        <p>The call fails with a <c>{badmap,Map}</c> exception if
-          <c><anno>Map</anno></c> is not a map.</p>
-        <p><em>Example:</em></p>
-        <code type="none">
-> M = maps:from_list([{I,I} || I &lt;- lists:seq(1,50)]).
-#{45 => 45,6 => 6,2 => 2,49 => 49,41 => 41,33 => 33,42 => 42,
-  43 => 43,10 => 10,9 => 9,19 => 19,14 => 14,5 => 5,18 => 18,
-  31 => 31,22 => 22,29 => 29,21 => 21,27 => 27,24 => 24,
-  47 => 47,40 => 40,30 => 30,23 => 23,28 => 28,46 => 46,
-  16 => 16,38 => 38,4 => 4,...}
-> MemoryIter = maps:iterator(M, #{ optimize => memory }), ok.
-ok
-> {K1, V1, _} = maps:next(MemoryIter), {K1, V1}.
-{46,46}
-> OrderedIter = maps:iterator(M, #{ ordered => true, optimize => memory }), ok.
-ok
-> {K2, V2, _} = maps:next(OrderedIter), {K2, V2}.
-{1,1}</code>
-      </desc>
-    </func>
-
     <func>
       <name name="keys" arity="1"/>
       <fsummary></fsummary>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 2f2dd41979..a13f340709 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -24,7 +24,7 @@
          map/2, size/1,
          update_with/3, update_with/4,
          without/2, with/2,
-         iterator/1, iterator/2, next/1]).
+         iterator/1, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -32,12 +32,14 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
--opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
-                    | list({term(), term()}).
+-opaque iterator() :: {term(), term(), iterator()}
+                      | none | nonempty_improper_list(integer(),map()).
 
 -export_type([iterator/0]).
 
--define(IS_ITERATOR(I), (is_list(I) orelse (is_map(element(2,I) andalso (is_list(element(1,I) orelse is_integer(element(1,I)))))))).
+-dialyzer({no_improper_lists, iterator/1}).
+
+-define(IS_ITERATOR(I), is_tuple(I) andalso tuple_size(I) == 3; I == none; is_integer(hd(I)) andalso is_map(tl(I))).
 
 %% Shadowed by erl_bif_types: maps:get/2
 -spec get(Key,Map) -> Value when
@@ -121,14 +123,20 @@ remove(_,_) -> erlang:nif_error(undef).
 
 take(_,_) -> erlang:nif_error(undef).
 
-%% Shadowed by erl_bif_types: maps:to_list/1
 -spec to_list(Map) -> [{Key,Value}] when
     Map :: map(),
     Key :: term(),
     Value :: term().
 
-to_list(_) -> erlang:nif_error(undef).
+to_list(Map) when is_map(Map) ->
+    to_list_internal(erts_internal:map_next(0, Map, []));
+to_list(Map) ->
+    erlang:error({badmap,Map},[Map]).
 
+to_list_internal([Iter, Map | Acc]) when is_integer(Iter) ->
+    to_list_internal(erts_internal:map_next(Iter, Map, Acc));
+to_list_internal(Acc) ->
+    Acc.
 
 %% Shadowed by erl_bif_types: maps:update/3
 -spec update(Key,Value,Map1) -> Map2 when
@@ -207,7 +215,7 @@ get(Key,Map,Default) ->
       Map :: map().
 
 filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
-    maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+    maps:from_list(filter_1(Pred, iterator(Map)));
 filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
     maps:from_list(filter_1(Pred, Iterator));
 filter(Pred,Map) ->
@@ -237,7 +245,7 @@ filter_1(Pred, Iter) ->
     V :: term().
 
 fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
-    lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+    fold_1(Fun,Init,iterator(Map));
 fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
     fold_1(Fun,Init,Iterator);
 fold(Fun,Init,Map) ->
@@ -260,7 +268,7 @@ fold_1(Fun, Acc, Iter) ->
     V2 :: term().
 
 map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
-    maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+    maps:from_list(map_1(Fun, iterator(Map)));
 map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
     maps:from_list(map_1(Fun, Iterator));
 map(Fun,Map) ->
@@ -286,42 +294,19 @@ size(Val) ->
       Map :: map(),
       Iterator :: iterator().
 
-iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) when is_map(M) -> [0 | M];
 iterator(M) -> erlang:error({badmap, M}, [M]).
 
--spec iterator(Map, Opts) -> Iterator when
-      Map :: map(),
-      Opts :: #{ ordered => boolean(), optimize => speed | memory },
-      Iterator :: iterator().
-iterator(M, Opts) when is_map(M), is_map(Opts) ->
-    case maps:merge(default_iterator_opts(), Opts) of
-        #{ ordered := true, optimize := speed} -> lists:sort(maps:to_list(M));
-        #{ ordered := false, optimize := speed} -> maps:to_list(M);
-        #{ ordered := true, optimize := memory} -> {lists:sort(maps:keys(M)), M};
-        #{ ordered := false, optimize := memory} -> {0, M}
-    end;
-iterator(M, Opts) when is_map(M) ->
-    erlang:error({badmap, M}, [M, Opts]);
-iterator(M, Opts) ->
-    erlang:error(error_type(M), [M, Opts]).
-
-default_iterator_opts() ->
-    #{ ordered => false, optimize => speed }.
-
 -spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
       Iterator :: iterator(),
       Key :: term(),
       Value :: term(),
       NextIterator :: iterator().
-next([{K, V} | T]) ->
-    {K, V, T};
-next([]) ->
-    none;
-next({I, M}) when is_map(M), is_integer(I) orelse is_atom(I) ->
-    erts_internal:map_next(I, M);
-next({[K | T], M}) when is_map(M) ->
-    {K, maps:get(K, M), {T, M}};
-next({[], M}) when is_map(M) ->
+next({K, V, I}) ->
+    {K, V, I};
+next([Path | Map]) when is_integer(Path), is_map(Map) ->
+    erts_internal:map_next(Path, Map, iterator);
+next(none) ->
     none;
 next(Iter) ->
     erlang:error(badarg, [Iter]).
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 0021dd0657..a75751b31d 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,7 +30,7 @@
 -export([t_update_with_3/1, t_update_with_4/1,
          t_get_3/1, t_filter_2/1,
          t_fold_3/1,t_map_2/1,t_size_1/1,
-         t_iterator_1/1, t_iterator_2/1,
+         t_iterator_1/1,
          t_with_2/1,t_without_2/1]).
 
 %%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -48,7 +48,7 @@ all() ->
     [t_update_with_3,t_update_with_4,
      t_get_3,t_filter_2,
      t_fold_3,t_map_2,t_size_1,
-     t_iterator_1, t_iterator_2,
+     t_iterator_1,
      t_with_2,t_without_2].
 
 t_update_with_3(Config) when is_list(Config) ->
@@ -179,40 +179,19 @@ t_iterator_1(Config) when is_list(Config) ->
 
     %% Large map test
 
-    Vs = lists:seq(1,200),
-    M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+    Vs2 = lists:seq(1,200),
+    M2 = maps:from_list([{{k,I},I}||I<-Vs2]),
     KVList2 = lists:sort(iter_kv(maps:iterator(M2))),
     KVList2 = lists:sort(maps:to_list(M2)),
-    ok.
 
-t_iterator_2(Config) when is_list(Config) ->
-
-    Vs = lists:seq(1,200),
-    Maps = [#{ a => 1, b => 2 }, maps:from_list([{{k,I},I}||I<-Vs])],
-    Optimize = [speed, memory],
-    Ordered = [true, false],
-
-    [test_iterator(Map, Opt, Ord) || Map <- Maps,
-                                     Opt <- Optimize,
-                                     Ord <- Ordered],
+    %% Larger map test
 
+    Vs3 = lists:seq(1,10000),
+    M3 = maps:from_list([{{k,I},I}||I<-Vs3]),
+    KVList3 = lists:sort(iter_kv(maps:iterator(M3))),
+    KVList3 = lists:sort(maps:to_list(M3)),
     ok.
 
-test_iterator(Map, Opt, Ord) ->
-    Opts = #{ optimize => Opt, ordered => Ord },
-    test_iterator_1(maps:iterator(Map, Opts), Map, Opts).
-
-test_iterator_1(Iter, OrigMap, Opts) ->
-    erlang:display(Opts),
-    KVs = iter_kv(Iter),
-    case Opts of
-        #{ ordered := true } ->
-            KVs = lists:sort(maps:to_list(OrigMap));
-        #{ ordered := false } ->
-            OrderedKVs = lists:sort(KVs),
-            OrderedKVs = lists:sort(maps:to_list(OrigMap))
-    end.
-
 iter_kv(I) ->
     case maps:next(I) of
         none ->
-- 
cgit v1.2.3


From f1666d981aab4e4cf94b91dc097675fa0b056c97 Mon Sep 17 00:00:00 2001
From: Lukas Larsson <lukas@erlang.org>
Date: Thu, 12 Oct 2017 15:55:04 +0200
Subject: stdlib: Make io_lib and io_lib_pretty use maps iterator

---
 lib/stdlib/src/io_lib.erl        | 13 ++++++++++++-
 lib/stdlib/src/io_lib_pretty.erl | 12 +++++++++++-
 lib/stdlib/test/io_SUITE.erl     |  4 ++--
 3 files changed, 25 insertions(+), 4 deletions(-)

(limited to 'lib/stdlib')

diff --git a/lib/stdlib/src/io_lib.erl b/lib/stdlib/src/io_lib.erl
index 9d447418f8..3c8430b820 100644
--- a/lib/stdlib/src/io_lib.erl
+++ b/lib/stdlib/src/io_lib.erl
@@ -963,7 +963,18 @@ limit_tail(Other, D) ->
 %% maps:from_list() creates a map with the same internal ordering of
 %% the selected associations as in Map.
 limit_map(Map, D) ->
-    maps:from_list(erts_internal:maps_to_list(Map, D)).
+    limit_map(maps:iterator(Map), D, []).
+
+limit_map(_I, 0, Acc) ->
+    maps:from_list(Acc);
+limit_map(I, D, Acc) ->
+    case maps:next(I) of
+        {K, V, NextI} ->
+            limit_map(NextI, D-1, [{K,V} | Acc]);
+        none ->
+            maps:from_list(Acc)
+    end.
+
 %%     maps:from_list(limit_map_body(erts_internal:maps_to_list(Map, D), D)).
 
 %% limit_map_body(_, 0) -> [{'...', '...'}];
diff --git a/lib/stdlib/src/io_lib_pretty.erl b/lib/stdlib/src/io_lib_pretty.erl
index 505613b80e..89e1931d2d 100644
--- a/lib/stdlib/src/io_lib_pretty.erl
+++ b/lib/stdlib/src/io_lib_pretty.erl
@@ -478,9 +478,19 @@ print_length(Term, _D, _RF, _Enc, _Str) ->
 print_length_map(_Map, 1, _RF, _Enc, _Str) ->
     {"#{...}", 6};
 print_length_map(Map, D, RF, Enc, Str) when is_map(Map) ->
-    Pairs = print_length_map_pairs(erts_internal:maps_to_list(Map, D), D, RF, Enc, Str),
+    Pairs = print_length_map_pairs(limit_map(maps:iterator(Map), D, []), D, RF, Enc, Str),
     {{map, Pairs}, list_length(Pairs, 3)}.
 
+limit_map(_I, 0, Acc) ->
+    Acc;
+limit_map(I, D, Acc) ->
+    case maps:next(I) of
+        {K, V, NextI} ->
+            limit_map(NextI, D-1, [{K,V} | Acc]);
+        none ->
+            Acc
+    end.
+
 print_length_map_pairs([], _D, _RF, _Enc, _Str) ->
     [];
 print_length_map_pairs(_Pairs, 1, _RF, _Enc, _Str) ->
diff --git a/lib/stdlib/test/io_SUITE.erl b/lib/stdlib/test/io_SUITE.erl
index e2c73371cd..13929bdbb6 100644
--- a/lib/stdlib/test/io_SUITE.erl
+++ b/lib/stdlib/test/io_SUITE.erl
@@ -2138,8 +2138,8 @@ otp_14175(_Config) ->
     "#{}" = p(#{}, 1),
     "#{...}" = p(#{a => 1}, 1),
     "#{#{} => a}" = p(#{#{} => a}, 2),
-    "#{a => 1,...}" = p(#{a => 1, b => 2}, 2),
-    "#{a => 1,b => 2}" = p(#{a => 1, b => 2}, -1),
+    mt("#{a => 1,...}", p(#{a => 1, b => 2}, 2)),
+    mt("#{a => 1,b => 2}", p(#{a => 1, b => 2}, -1)),
 
     M = #{kaaaaaaaaaaaaaaaaaaa => v1,kbbbbbbbbbbbbbbbbbbb => v2,
           kccccccccccccccccccc => v3,kddddddddddddddddddd => v4,
-- 
cgit v1.2.3