The R13B03 release.OTP_R13B03

1 files changed, 428 insertions, 0 deletions

diff --git a/lib/compiler/src/cerl_clauses.erl b/lib/compiler/src/cerl_clauses.erl
new file mode 100644
index 0000000000..5f111a5e05
--- /dev/null
+++ b/lib/compiler/src/cerl_clauses.erl
@@ -0,0 +1,428 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-2009. All Rights Reserved.
+%% 
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%% 
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%% 
+%% %CopyrightEnd%
+
+%% @doc Utility functions for Core Erlang case/receive clauses.
+%%
+%% <p>Syntax trees are defined in the module <a
+%% href=""><code>cerl</code></a>.</p>
+%%
+%% @type cerl() = cerl:cerl()
+
+-module(cerl_clauses).
+
+-export([any_catchall/1, eval_guard/1, is_catchall/1, match/2,
+	 match_list/2, reduce/1, reduce/2]).
+
+-import(cerl, [alias_pat/1, alias_var/1, data_arity/1, data_es/1,
+	       data_type/1, clause_guard/1, clause_pats/1, concrete/1,
+	       is_data/1, is_c_var/1, let_body/1, letrec_body/1,
+	       seq_body/1, try_arg/1, type/1, values_es/1]).
+
+%% ---------------------------------------------------------------------
+
+%% @spec is_catchall(Clause::cerl()) -> boolean()
+%%
+%% @doc Returns <code>true</code> if an abstract clause is a
+%% catch-all, otherwise <code>false</code>. A clause is a catch-all if
+%% all its patterns are variables, and its guard expression always
+%% evaluates to <code>true</code>; cf. <code>eval_guard/1</code>.
+%%
+%% <p>Note: <code>Clause</code> must have type
+%% <code>clause</code>.</p>
+%%
+%% @see eval_guard/1
+%% @see any_catchall/1
+
+-spec is_catchall(cerl:c_clause()) -> boolean().
+
+is_catchall(C) ->
+    case all_vars(clause_pats(C)) of
+	true ->
+	    case eval_guard(clause_guard(C)) of
+		{value, true} ->
+		    true;
+		_ ->
+		    false
+	    end;
+	false ->
+	    false
+    end.
+
+all_vars([C | Cs]) ->
+    case is_c_var(C) of
+	true ->
+	    all_vars(Cs);
+	false ->
+	    false
+    end;
+all_vars([]) ->
+    true.
+
+
+%% @spec any_catchall(Clauses::[cerl()]) -> boolean()
+%%
+%% @doc Returns <code>true</code> if any of the abstract clauses in
+%% the list is a catch-all, otherwise <code>false</code>.  See
+%% <code>is_catchall/1</code> for details.
+%%
+%% <p>Note: each node in <code>Clauses</code> must have type
+%% <code>clause</code>.</p>
+%%
+%% @see is_catchall/1
+
+-spec any_catchall([cerl:cerl()]) -> boolean().
+
+any_catchall([C | Cs]) ->
+    case is_catchall(C) of
+	true ->
+	    true;
+	false ->
+	    any_catchall(Cs)
+    end;
+any_catchall([]) ->
+    false.
+
+
+%% @spec eval_guard(Expr::cerl()) -> none | {value, term()}
+%%
+%% @doc Tries to reduce a guard expression to a single constant value,
+%% if possible. The returned value is <code>{value, Term}</code> if the
+%% guard expression <code>Expr</code> always yields the constant value
+%% <code>Term</code>, and is otherwise <code>none</code>.
+%%
+%% <p>Note that although guard expressions should only yield boolean
+%% values, this function does not guarantee that <code>Term</code> is
+%% either <code>true</code> or <code>false</code>. Also note that only
+%% simple constructs like let-expressions are examined recursively;
+%% general constant folding is not performed.</p>
+%%
+%% @see is_catchall/1
+
+%% This function could possibly be improved further, but constant
+%% folding should in general be performed elsewhere.
+
+-spec eval_guard(cerl:cerl()) -> 'none' | {'value', term()}.
+
+eval_guard(E) ->
+    case type(E) of
+	literal ->
+	    {value, concrete(E)};
+	values ->
+	    case values_es(E) of
+		[E1] ->
+		    eval_guard(E1);
+		_ ->
+		    none
+	    end;
+	'try' ->
+	    eval_guard(try_arg(E));
+	seq ->
+	    eval_guard(seq_body(E));
+	'let' ->
+	    eval_guard(let_body(E));
+	'letrec' ->
+	    eval_guard(letrec_body(E));
+	_ ->
+	    none
+    end.
+
+
+%% ---------------------------------------------------------------------
+
+-type bindings() :: [{cerl:cerl(), cerl:cerl()}].
+
+%% @spec reduce(Clauses) -> {true, {Clause, Bindings}}
+%%                        | {false, Clauses}
+%%
+%% @equiv reduce(Cs, [])
+
+-spec reduce([cerl:c_clause()]) ->
+        {'true', {cerl:c_clause(), bindings()}} | {'false', [cerl:c_clause()]}.
+
+reduce(Cs) ->
+    reduce(Cs, []).
+
+%% @spec reduce(Clauses::[Clause], Exprs::[Expr]) ->
+%%           {true, {Clause, Bindings}}
+%%         | {false, [Clause]}
+%%
+%%    Clause = cerl()
+%%    Expr = any | cerl()
+%%    Bindings = [{cerl(), cerl()}]
+%%
+%% @doc Selects a single clause, if possible, or otherwise reduces the
+%% list of selectable clauses. The input is a list <code>Clauses</code>
+%% of abstract clauses (i.e., syntax trees of type <code>clause</code>),
+%% and a list of switch expressions <code>Exprs</code>. The function
+%% tries to uniquely select a single clause or discard unselectable
+%% clauses, with respect to the switch expressions. All abstract clauses
+%% in the list must have the same number of patterns. If
+%% <code>Exprs</code> is not the empty list, it must have the same
+%% length as the number of patterns in each clause; see
+%% <code>match_list/2</code> for details.
+%% 
+%% <p>A clause can only be selected if its guard expression always
+%% yields the atom <code>true</code>, and a clause whose guard
+%% expression always yields the atom <code>false</code> can never be
+%% selected. Other guard expressions are considered to have unknown
+%% value; cf. <code>eval_guard/1</code>.</p>
+%%
+%% <p>If a particular clause can be selected, the function returns
+%% <code>{true, {Clause, Bindings}}</code>, where <code>Clause</code> is
+%% the selected clause and <code>Bindings</code> is a list of pairs
+%% <code>{Var, SubExpr}</code> associating the variables occurring in
+%% the patterns of <code>Clause</code> with the corresponding
+%% subexpressions in <code>Exprs</code>. The list of bindings is given
+%% in innermost-first order; see the <code>match/2</code> function for
+%% details.</p>
+%% 
+%% <p>If no clause could be definitely selected, the function returns
+%% <code>{false, NewClauses}</code>, where <code>NewClauses</code> is
+%% the list of entries in <code>Clauses</code> that remain after
+%% eliminating unselectable clauses, preserving the relative order.</p>
+%%
+%% @see eval_guard/1
+%% @see match/2
+%% @see match_list/2
+
+-type expr() :: 'any' | cerl:cerl().
+
+-spec reduce([cerl:c_clause()], [expr()]) ->
+        {'true', {cerl:c_clause(), bindings()}} | {'false', [cerl:c_clause()]}.
+
+reduce(Cs, Es) ->
+    reduce(Cs, Es, []).
+
+reduce([C | Cs], Es, Cs1) ->
+    Ps = clause_pats(C),
+    case match_list(Ps, Es) of
+	none ->
+	    %% Here, we know that the current clause cannot possibly be
+	    %% selected, so we drop it and visit the rest.
+	    reduce(Cs, Es, Cs1);
+	{false, _} ->
+	    %% We are not sure if this clause might be selected, so we
+	    %% save it and visit the rest.
+	    reduce(Cs, Es, [C | Cs1]);
+	{true, Bs} ->
+	    case eval_guard(clause_guard(C)) of
+		{value, true} when Cs1 =:= [] ->
+		    %% We have a definite match - we return the residual
+		    %% expression and signal that a selection has been
+		    %% made. All other clauses are dropped.
+		    {true, {C, Bs}};
+		{value, true} ->
+		    %% Unless one of the previous clauses is selected,
+		    %% this clause will definitely be, so we can drop
+		    %% the rest.
+		    {false, lists:reverse([C | Cs1])};
+		{value, false} ->
+		    %% This clause can never be selected, since its
+		    %% guard is never 'true', so we drop it.
+		    reduce(Cs, Es, Cs1);
+		_ ->
+		    %% We are not sure if this clause might be selected
+		    %% (or might even cause a crash), so we save it and
+		    %% visit the rest.
+		    reduce(Cs, Es, [C | Cs1])
+	    end
+    end;
+reduce([], _, Cs) ->
+    %% All clauses visited, without a complete match. Signal "not
+    %% reduced" and return the saved clauses, in the correct order.
+    {false, lists:reverse(Cs)}.
+
+
+%% ---------------------------------------------------------------------
+
+%% @spec match(Pattern::cerl(), Expr) ->
+%%           none | {true, Bindings} | {false, Bindings}
+%%
+%%     Expr = any | cerl()
+%%     Bindings = [{cerl(), Expr}]
+%%
+%% @doc Matches a pattern against an expression. The returned value is
+%% <code>none</code> if a match is impossible, <code>{true,
+%% Bindings}</code> if <code>Pattern</code> definitely matches
+%% <code>Expr</code>, and <code>{false, Bindings}</code> if a match is
+%% not definite, but cannot be excluded. <code>Bindings</code> is then
+%% a list of pairs <code>{Var, SubExpr}</code>, associating each
+%% variable in the pattern with either the corresponding subexpression
+%% of <code>Expr</code>, or with the atom <code>any</code> if no
+%% matching subexpression exists. (Recall that variables may not be
+%% repeated in a Core Erlang pattern.) The list of bindings is given
+%% in innermost-first order; this should only be of interest if
+%% <code>Pattern</code> contains one or more alias patterns. If the
+%% returned value is <code>{true, []}</code>, it implies that the
+%% pattern and the expression are syntactically identical.
+%%
+%% <p>Instead of a syntax tree, the atom <code>any</code> can be
+%% passed for <code>Expr</code> (or, more generally, be used for any
+%% subtree of <code>Expr</code>, in as much the abstract syntax tree
+%% implementation allows it); this means that it cannot be decided
+%% whether the pattern will match or not, and the corresponding
+%% variable bindings will all map to <code>any</code>. The typical use
+%% is for producing bindings for <code>receive</code> clauses.</p>
+%%
+%% <p>Note: Binary-syntax patterns are never structurally matched
+%% against binary-syntax expressions by this function.</p>
+%%
+%% <p>Examples:
+%% <ul>
+%%   <li>Matching a pattern "<code>{X, Y}</code>" against the
+%%   expression "<code>{foo, f(Z)}</code>" yields <code>{true,
+%%   Bindings}</code> where <code>Bindings</code> associates
+%%   "<code>X</code>" with the subtree "<code>foo</code>" and
+%%   "<code>Y</code>" with the subtree "<code>f(Z)</code>".</li>
+%%
+%%   <li>Matching pattern "<code>{X, {bar, Y}}</code>" against
+%%   expression "<code>{foo, f(Z)}</code>" yields <code>{false,
+%%   Bindings}</code> where <code>Bindings</code> associates
+%%   "<code>X</code>" with the subtree "<code>foo</code>" and
+%%   "<code>Y</code>" with <code>any</code> (because it is not known
+%%   if "<code>{foo, Y}</code>" might match the run-time value of
+%%   "<code>f(Z)</code>" or not).</li>
+%%
+%%   <li>Matching pattern "<code>{foo, bar}</code>" against expression
+%%   "<code>{foo, f()}</code>" yields <code>{false, []}</code>,
+%%   telling us that there might be a match, but we cannot deduce any
+%%   bindings.</li>
+%%
+%%   <li>Matching <code>{foo, X = {bar, Y}}</code> against expression
+%%   "<code>{foo, {bar, baz}}</code>" yields <code>{true,
+%%   Bindings}</code> where <code>Bindings</code> associates
+%%   "<code>Y</code>" with "<code>baz</code>", and "<code>X</code>"
+%%   with "<code>{bar, baz}</code>".</li>
+%%
+%%   <li>Matching a pattern "<code>{X, Y}</code>" against
+%%   <code>any</code> yields <code>{false, Bindings}</code> where
+%%   <code>Bindings</code> associates both "<code>X</code>" and
+%%   "<code>Y</code>" with <code>any</code>.</li>
+%% </ul></p>
+
+-type match_ret() :: 'none' | {'true', bindings()} | {'false', bindings()}.
+
+-spec match(cerl:cerl(), expr()) -> match_ret().
+
+match(P, E) ->
+    match(P, E, []).
+
+match(P, E, Bs) ->
+    case type(P) of
+	var ->
+	    %% Variables always match, since they cannot have repeated
+	    %% occurrences in a pattern.
+	    {true, [{P, E} | Bs]};
+	alias ->
+	    %% All variables in P1 will be listed before the alias
+	    %% variable in the result.
+	    match(alias_pat(P), E, [{alias_var(P), E} | Bs]);
+	binary ->
+	    %% The most we can do is to say "definitely no match" if a
+	    %% binary pattern is matched against non-binary data.
+	    if E =:= any ->
+		    {false, Bs};
+	       true ->
+		    case is_data(E) of
+			true ->
+			    none;
+			false ->
+			    {false, Bs}
+		    end
+	    end;
+	_ ->
+	    match_1(P, E, Bs)
+    end.
+
+match_1(P, E, Bs) ->
+    case is_data(P) of
+	true when E =:= any ->
+	    %% If we don't know the structure of the value of E at this
+	    %% point, we just match the subpatterns against 'any', and
+	    %% make sure the result is a "maybe".
+	    Ps = data_es(P),
+	    Es = [any || _ <- Ps],
+	    case match_list(Ps, Es, Bs) of
+		{_, Bs1} ->
+		    {false, Bs1};
+		none ->
+		    none
+	    end;
+	true ->
+	    %% Test if the expression represents a constructor
+	    case is_data(E) of
+		true ->
+		    T1 = {data_type(E), data_arity(E)},
+		    T2 = {data_type(P), data_arity(P)},
+		    %% Note that we must test for exact equality.
+		    if T1 =:= T2 ->
+			    match_list(data_es(P), data_es(E), Bs);
+		       true ->
+			    none
+		    end;
+		false ->
+		    %% We don't know the run-time structure of E, and P
+		    %% is not a variable or an alias pattern, so we
+		    %% match against 'any' instead.
+		    match_1(P, any, Bs)
+	    end;
+	false ->
+	    %% Strange pattern - give up, but don't say "no match".
+	    {false, Bs}
+    end.
+
+
+%% @spec match_list(Patterns::[cerl()], Exprs::[Expr]) ->
+%%           none | {true, Bindings} | {false, Bindings}
+%%
+%%     Expr = any | cerl()
+%%     Bindings = [{cerl(), cerl()}]
+%%
+%% @doc Like <code>match/2</code>, but matching a sequence of patterns
+%% against a sequence of expressions. Passing an empty list for
+%% <code>Exprs</code> is equivalent to passing a list of
+%% <code>any</code> atoms of the same length as <code>Patterns</code>.
+%%
+%% @see match/2
+
+-spec match_list([cerl:cerl()], [expr()]) -> match_ret().
+
+match_list([], []) ->
+    {true, []};    % no patterns always match
+match_list(Ps, []) ->
+    match_list(Ps, [any || _ <- Ps], []);
+match_list(Ps, Es) ->
+    match_list(Ps, Es, []).
+
+match_list([P | Ps], [E | Es], Bs) ->
+    case match(P, E, Bs) of
+	{true, Bs1} ->
+	    match_list(Ps, Es, Bs1);
+	{false, Bs1} ->
+	    %% Make sure "maybe" is preserved
+	    case match_list(Ps, Es, Bs1) of
+		{_, Bs2} ->
+		    {false, Bs2};
+		none ->
+		    none
+	    end;
+	none ->
+	    none
+    end;
+match_list([], [], Bs) ->
+    {true, Bs}.