%% %% %CopyrightBegin% %% %% Copyright Ericsson AB 2001-2010. 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}.