nm

An OTP library for transforming deeply nested maps and lists without rebuilding every enclosing parent by hand. You unnest your data into an ETS table, read and change the parts you need through references, then nest the table back into ordinary data.

Build

$ rebar3 compile

To run the Erlang examples below, start a shell with nm loaded from the repository root:

$ rebar3 shell

Unnest your data

nm:unnest/1 copies a nested map or list into a new ETS table and returns {ok, Table}. Each nested map or list is replaced by a reference, so you can change one part without rebuilding its parents.

Round trip:

{ok, T} = nm:unnest(#{<<"a">> => 1, <<"nested">> => #{<<"value">> => 2}}),
{ok, Root} = nm:get_value(T, root),
{'$nm_ref', ChildId} = maps:get(<<"nested">>, Root),
{ok, Child} = nm:get_value(T, ChildId),
ok = nm:fast_update(T, ChildId, Child#{<<"count">> => 1}),
{ok, Nested} = nm:nest(T),
Nested = #{<<"a">> => 1, <<"nested">> => #{<<"value">> => 2, <<"count">> => 1}}.

Success return shapes: nm:unnest/1 returns {ok, Table}, nm:get_value/2 returns {ok, Value}, nm:fast_update/3 returns ok, and nm:nest/1 returns {ok, Nested}. The last line is a match, so it only succeeds when the nested result equals the expected value.

Read root, follow refs, work with ids

nm:get_value/2 returns the local value of a node. Nested children inside it appear as {'$nm_ref', Id}. To follow one, take Id out of the tuple and pass that binary to get_value/2, fast_update/3, or update/3. Pass the id, not the whole {'$nm_ref', Id} tuple: the tuple is rejected with {error, not_an_id}. The atom root is the id of the top-level value.

Ids are opaque. Pass them around, but don't depend on their contents.

Change values

Use nm:fast_update/3 for literal edits (adding or overwriting a field) or for rearranging existing refs. Children are kept as they are. Use nm:update/3 for structural changes; see "Choose the right update operation" below.

Choose the right update operation

• nm:get_value/2 reads a node's local value. It may still contain refs.
• nm:fast_update/3 edits literals or rearranges existing refs without changing child relationships. Use it for things like adding a new field to a map.
• For structural changes, nm:partial_nest/2 returns the subtree as ordinary nested data. Transform it, then pass it to nm:update/3, which discards the node's children and unnests the new value.
• nm:nest/1 returns the complete ordinary structure.

Nest the result back

nm:nest/1 returns {ok, Nested}, the complete ordinary structure. It does not remove anything from the table, so you can keep working with the table afterwards.

Ownership, lifetime, and supported data

• The table is initially owned by the process that calls nm:unnest/1. It is protected: the current owner can write, and other processes can only read. Make updates from the owner. nm has no ownership-transfer function of its own, but the table is a normal ETS table, so standard primitives such as ets:give_away/3 work on it. A caller who uses one hands the table to another process, and that process becomes the owner.
• Owner termination destroys the table. Don't hold a table across a process boundary expecting it to outlive the caller. nm:nest/1 does not dispose of the table.
• Maps and lists are nested. Tuples stay literal, including any maps or lists inside them. A list of tuples, such as a proplist, has its outer list traversed while each tuple stays as it is.
• Map keys keep their original types.
• The worked traversal example below assumes a specific input shape and does not validate malformed input in general. See that section for the exact fields it expects.
• No concurrent-write guarantees are made.

Worked traversal

The example is a position-numbering pass over a list of courses. Each course is a map with a name, a lessons list of lesson maps, and a boolean reset_lesson_position flag. The pass adds a position field to each course and to each lesson. Lesson numbering carries forward across courses unless a course sets reset_lesson_position to true.

The input has three courses:

Course A: two lessons, reset false   -> course position 1, lesson positions 1, 2
Course B: one lesson,  reset false   -> course position 2, lesson position 3
Course C: two lessons, reset true    -> course position 3, lesson positions 1, 2

Course positions are independent: 1, 2, 3.

The traversal makes these decisions:

• Start at root.
• Follow each course's ref and its lessons-list ref.
• Add or change the literal position fields with fast_update/3.
• Carry lesson numbering forward unless the course requests a reset.
• Nest once, after the traversal.

Both listings below are the complete module source. Paste each into the shell you started in Build.

Keys: the Erlang <<"lessons">> and the Elixir "lessons" are the same binary key. nm keeps the key types you give it. An Erlang "lessons" is a charlist instead, which is not the same key as <<"lessons">>.

Erlang

The module below declares -module(traversal).. It is the readable source; the shell block after it writes this same module to a temp path, compiles it, loads it, and deletes the temp file:

-module(traversal).

-export([traverse/1]).

traverse(Data) ->
    {ok, Table} = nm:unnest(Data),
    {ok, Root} = nm:get_value(Table, root),
    lists:foldl(fun root_traversal/2, {Table, 1, 1}, Root),
    nm:nest(Table).

root_traversal({'$nm_ref', Id}, {Table, C10, C20}) ->
    {ok, Current} = nm:get_value(Table, Id),
    {'$nm_ref', ListId} = maps:get(<<"lessons">>, Current),
    {ok, Lessons} = nm:get_value(Table, ListId),
    Updated = maps:put(<<"position">>, C10, Current),
    nm:fast_update(Table, Id, Updated),
    C21 =
        case maps:get(<<"reset_lesson_position">>, Current) of
            true -> 1;
            false -> C20
        end,
    {_, C22} = lists:foldl(fun lessons_traversal/2, {Table, C21}, Lessons),
    {Table, C10 + 1, C22}.

lessons_traversal({'$nm_ref', Id}, {Table, C0}) ->
    {ok, Current} = nm:get_value(Table, Id),
    Updated = maps:put(<<"position">>, C0, Current),
    nm:fast_update(Table, Id, Updated),
    {Table, C0 + 1}.

Load it without relying on any file the reader already has. This block writes the module above to a temp path, compiles it, loads the resulting beam, runs it, then deletes the temp file:

Src =
    "-module(traversal).\n"
    "\n"
    "-export([traverse/1]).\n"
    "\n"
    "traverse(Data) ->\n"
    "    {ok, Table} = nm:unnest(Data),\n"
    "    {ok, Root} = nm:get_value(Table, root),\n"
    "    lists:foldl(fun root_traversal/2, {Table, 1, 1}, Root),\n"
    "    nm:nest(Table).\n"
    "\n"
    "root_traversal({'$nm_ref', Id}, {Table, C10, C20}) ->\n"
    "    {ok, Current} = nm:get_value(Table, Id),\n"
    "    {'$nm_ref', ListId} = maps:get(<<\"lessons\">>, Current),\n"
    "    {ok, Lessons} = nm:get_value(Table, ListId),\n"
    "    Updated = maps:put(<<\"position\">>, C10, Current),\n"
    "    nm:fast_update(Table, Id, Updated),\n"
    "    C21 =\n"
    "        case maps:get(<<\"reset_lesson_position\">>, Current) of\n"
    "            true -> 1;\n"
    "            false -> C20\n"
    "        end,\n"
    "    {_, C22} = lists:foldl(fun lessons_traversal/2, {Table, C21}, Lessons),\n"
    "    {Table, C10 + 1, C22}.\n"
    "\n"
    "lessons_traversal({'$nm_ref', Id}, {Table, C0}) ->\n"
    "    {ok, Current} = nm:get_value(Table, Id),\n"
    "    Updated = maps:put(<<\"position\">>, C0, Current),\n"
    "    nm:fast_update(Table, Id, Updated),\n"
    "    {Table, C0 + 1}.\n",
Path = "/tmp/traversal_doc_example.erl",
ok = file:write_file(Path, Src),
{ok, traversal, Bin} = compile:file(Path, [binary]),
{module, traversal} = code:load_binary(traversal, "traversal.beam", Bin),
Data = [
    #{<<"name">> => <<"Course A">>,
      <<"lessons">> => [#{<<"title">> => <<"a1">>}, #{<<"title">> => <<"a2">>}],
      <<"reset_lesson_position">> => false},
    #{<<"name">> => <<"Course B">>,
      <<"lessons">> => [#{<<"title">> => <<"b1">>}],
      <<"reset_lesson_position">> => false},
    #{<<"name">> => <<"Course C">>,
      <<"lessons">> => [#{<<"title">> => <<"c1">>}, #{<<"title">> => <<"c2">>}],
      <<"reset_lesson_position">> => true}
],
{ok, Result} = traversal:traverse(Data),
Expected = [
    #{<<"name">> => <<"Course A">>, <<"position">> => 1, <<"reset_lesson_position">> => false,
      <<"lessons">> => [#{<<"title">> => <<"a1">>, <<"position">> => 1},
                        #{<<"title">> => <<"a2">>, <<"position">> => 2}]},
    #{<<"name">> => <<"Course B">>, <<"position">> => 2, <<"reset_lesson_position">> => false,
      <<"lessons">> => [#{<<"title">> => <<"b1">>, <<"position">> => 3}]},
    #{<<"name">> => <<"Course C">>, <<"position">> => 3, <<"reset_lesson_position">> => true,
      <<"lessons">> => [#{<<"title">> => <<"c1">>, <<"position">> => 1},
                        #{<<"title">> => <<"c2">>, <<"position">> => 2}]}
],
Result = Expected,
file:delete(Path).

traverse/1 returns {ok, Result}. The result is ordinary nested data, so it can be traversed again with the same output.

Elixir

The Elixir module is the same algorithm. The fenced defmodule below is the complete module:

defmodule Traversal do
  def traverse(data) do
    {:ok, t} = :nm.unnest(data)
    {:ok, root} = :nm.get_value(t, :root)
    Enum.reduce(root, {t, 1, 1}, &root_traversal/2)

    :nm.nest(t)
  end

  defp root_traversal({:"$nm_ref", id}, {t, c1, c2}) do
    {:ok, current} = :nm.get_value(t, id)
    {:"$nm_ref", list_id} = current["lessons"]
    {:ok, list} = :nm.get_value(t, list_id)

    updated = Map.put(current, "position", c1)
    :nm.fast_update(t, id, updated)

    c2 = if current["reset_lesson_position"], do: 1, else: c2
    {_, c2} = Enum.reduce(list, {t, c2}, &lessons_traversal/2)
    {t, c1 + 1, c2}
  end

  defp lessons_traversal({:"$nm_ref", id}, {t, c}) do
    {:ok, current} = :nm.get_value(t, id)
    updated = Map.put(current, "position", c)
    :nm.fast_update(t, id, updated)

    {t, c + 1}
  end
end

Run it with the same input and expected output:

data = [
  %{"name" => "Course A", "lessons" => [%{"title" => "a1"}, %{"title" => "a2"}],
    "reset_lesson_position" => false},
  %{"name" => "Course B", "lessons" => [%{"title" => "b1"}],
    "reset_lesson_position" => false},
  %{"name" => "Course C", "lessons" => [%{"title" => "c1"}, %{"title" => "c2"}],
    "reset_lesson_position" => true}
]

{:ok, result} = Traversal.traverse(data)

expected = [
  %{"name" => "Course A", "position" => 1, "reset_lesson_position" => false,
    "lessons" => [%{"title" => "a1", "position" => 1}, %{"title" => "a2", "position" => 2}]},
  %{"name" => "Course B", "position" => 2, "reset_lesson_position" => false,
    "lessons" => [%{"title" => "b1", "position" => 3}]},
  %{"name" => "Course C", "position" => 3, "reset_lesson_position" => true,
    "lessons" => [%{"title" => "c1", "position" => 1}, %{"title" => "c2", "position" => 2}]}
]

^expected = result

Traversal.traverse/1 returns {:ok, result}. From the repository root, start an interactive session that puts nm on the path:

$ iex -pa _build/default/lib/nm/ebin

Then paste the defmodule block, and then the input block, into that session.