diff options
author | Lukas Larsson <[email protected]> | 2011-03-09 13:29:48 +0100 |
---|---|---|
committer | Lukas Larsson <[email protected]> | 2011-03-09 13:29:48 +0100 |
commit | b6637f53cc885c336e3001617d742d79216c80e3 (patch) | |
tree | ec92e4ebe5c2774a671ba5eba8032ca179339951 /lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl | |
parent | 62e056af8c4fa058faa5087614c6b837a07f06e6 (diff) | |
parent | dd14097487c33ac4d1ceed36b96070feb545219f (diff) | |
download | otp-b6637f53cc885c336e3001617d742d79216c80e3.tar.gz otp-b6637f53cc885c336e3001617d742d79216c80e3.tar.bz2 otp-b6637f53cc885c336e3001617d742d79216c80e3.zip |
Merge branch 'aronisstav/dialyzer/dialyzer_tests/OTP-9116' into dev
* aronisstav/dialyzer/dialyzer_tests/OTP-9116:
Increase timetrap of options1 suite
Write output_plt even when plt_check is ok
Create plt with erts, kernel and stdlib only
Update test results as they currently appear in dev
Major restructure of dialyzer's testsuite
Add 'apps' option to the erlang interface
Update spec file to work with new common test structure
Test suites for Dialyzer
Diffstat (limited to 'lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl')
-rw-r--r-- | lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl | 409 |
1 files changed, 409 insertions, 0 deletions
diff --git a/lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl b/lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl new file mode 100644 index 0000000000..f207178f13 --- /dev/null +++ b/lib/dialyzer/test/options1_tests_SUITE_data/src/compiler/cerl_clauses.erl @@ -0,0 +1,409 @@ +%% ``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 via the world wide web 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. +%% +%% The Initial Developer of the Original Code is Richard Carlsson. +%% Copyright (C) 1999-2002 Richard Carlsson. +%% Portions created by Ericsson are Copyright 2001, Ericsson Utvecklings +%% AB. All Rights Reserved.'' +%% +%% $Id: cerl_clauses.erl,v 1.2 2009/09/17 09:46:19 kostis Exp $ + +%% @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]). + +-import(lists, [reverse/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 + +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 + +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. + +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. + + +%% --------------------------------------------------------------------- + +%% @spec reduce(Clauses) -> {true, {Clauses, Bindings}} +%% | {false, Clauses} +%% +%% @equiv reduce(Cs, []) + +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 + +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, 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, 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> + +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 = lists:duplicate(length(Ps), any), + 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 + +match_list([], []) -> + {true, []}; % no patterns always match +match_list(Ps, []) -> + match_list(Ps, lists:duplicate(length(Ps), any), []); +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}. |