path: root/lib/compiler/src/cerl_clauses.erl

%%
%% %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 type(E) of
			literal ->
			    case is_bitstring(concrete(E)) of
				false ->
				    none;
				true ->
				    {false, Bs}
			    end;
			cons ->
			    none;
			tuple ->
			    none;
			_ ->
			    {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}.