Add some internal documentation about cerl_clauses

I recently tried to add some additional optimizations for
matching of maps, but found out that the inliner will need
some updates to be able to handle those optimizations.

Add lib/compiler/internal_doc/cerl-notes.md to document what
I've learned.

2 files changed, 77 insertions, 0 deletions

diff --git a/lib/compiler/internal_doc/cerl-notes.md b/lib/compiler/internal_doc/cerl-notes.md
new file mode 100644
index 0000000000..705fe8f42d
--- /dev/null
+++ b/lib/compiler/internal_doc/cerl-notes.md
@@ -0,0 +1,75 @@
+Some notes on the cerl modules
+==============================
+
+Maps in cerl_clauses:match/3
+----------------------------
+
+Not much optimization is done for maps in `cerl_clauses:match/3`.
+
+The reason is that the inliner (`cerl_inline`) was not designed for
+data types that depend on variables bound in the enclosing environment
+(for example, the keys for maps).  If we attempt to extend the
+optimizations for maps similar to the optimizations for the other data
+types, the inliner will crash for certain code.  Here is an example of
+code that would crash the inliner:
+
+     t() ->
+        f(key).
+
+     f(K) ->
+        case #{K => value} of
+          #{key := V} -> V
+        end.
+
+The reason for the crash is that the inliner works in several
+passes and calls `cerl_clauses:match/3` twice.  The inliner will
+assume that the same result will be returned both times, but
+for this example different bindings will be returned.
+
+Here is the rough outline of what happens:
+
+* The first time `cerl_clauses:match/3` will be asked to match the
+pattern `#{K := V}` against `#{key => value}`. It cannot say more
+than that the pattern *may* match.
+
+* Now the inliner will add the bindings to body of the clause (which
+is simply `V`).  In this case, the bindings are still empty, so
+nothing is added.
+
+* The inliner will now do some substitutions and renaming.  The
+variable `K` will be replaced with `key`.
+
+* The next time `cerl_clauses:match/3` is called, it will be asked to
+match the pattern `#{key := V}` against `#{key => value#}`.  In this
+case, there will be a match and the bindings can be extended with
+`{V,value}`.
+
+* The inliner will see that the entire case can be removed.  Only
+the body for the clause needs to be kept.
+
+Thus, after inlining the function `t/0` will look like this:
+
+     t() ->
+        V.
+
+The problem here is that the inliner assumed that the bindings from
+the first and second call to `cer_clauses:match/3` would be the same.
+It used the empty bindings from the first call for the body.
+
+The correct way would be to add the bindings from the second call:
+
+     t() ->
+        let V = value in V.
+
+### How to fix this ###
+
+The inliner will need to call `cerl_clauses:match/3` after doing
+all substitutions and renaming.  It is not clear to me how difficult
+that would be.  I assume that the inliner is written the way it is
+for a good reason.  That means that switching the order things are
+done would lead to correctness and/or performance problems.
+
+### What must also be done to fix this ###
+
+`cerl_inline:make_template/3` must be extended to create a template
+for maps.  That is relatively straightforward.
diff --git a/lib/compiler/src/cerl_clauses.erl b/lib/compiler/src/cerl_clauses.erl
index 7d6518c3c6..fa5104c01b 100644
--- a/lib/compiler/src/cerl_clauses.erl
+++ b/lib/compiler/src/cerl_clauses.erl
@@ -353,6 +353,8 @@ match(P, E, Bs) ->
 	map ->
 	    %% The most we can do is to say "definitely no match" if a
 	    %% map pattern is matched against non-map data.
+            %% (Note: See the document internal_doc/cerl-notes.md for
+            %% information why we don't try to do more here.)
 	    case E of
 		any ->
 		    {false, Bs};