1%% ``Licensed under the Apache License, Version 2.0 (the "License"); 2%% you may not use this file except in compliance with the License. 3%% You may obtain a copy of the License at 4%% 5%% http://www.apache.org/licenses/LICENSE-2.0 6%% 7%% Unless required by applicable law or agreed to in writing, software 8%% distributed under the License is distributed on an "AS IS" BASIS, 9%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 10%% See the License for the specific language governing permissions and 11%% limitations under the License. 12%% 13%% The Initial Developer of the Original Code is Richard Carlsson. 14%% Copyright (C) 1999-2002 Richard Carlsson. 15%% Portions created by Ericsson are Copyright 2001, Ericsson Utvecklings 16%% AB. All Rights Reserved.'' 17%% 18%% $Id: cerl_clauses.erl,v 1.2 2009/09/17 09:46:19 kostis Exp $ 19 20%% @doc Utility functions for Core Erlang case/receive clauses. 21%% 22%% <p>Syntax trees are defined in the module <a 23%% href=""><code>cerl</code></a>.</p> 24%% 25%% @type cerl() = cerl:cerl() 26 27-module(cerl_clauses). 28 29-export([any_catchall/1, eval_guard/1, is_catchall/1, match/2, 30 match_list/2, reduce/1, reduce/2]). 31 32-import(cerl, [alias_pat/1, alias_var/1, data_arity/1, data_es/1, 33 data_type/1, clause_guard/1, clause_pats/1, concrete/1, 34 is_data/1, is_c_var/1, let_body/1, letrec_body/1, 35 seq_body/1, try_arg/1, type/1, values_es/1]). 36 37-import(lists, [reverse/1]). 38 39 40%% --------------------------------------------------------------------- 41 42%% @spec is_catchall(Clause::cerl()) -> boolean() 43%% 44%% @doc Returns <code>true</code> if an abstract clause is a 45%% catch-all, otherwise <code>false</code>. A clause is a catch-all if 46%% all its patterns are variables, and its guard expression always 47%% evaluates to <code>true</code>; cf. <code>eval_guard/1</code>. 48%% 49%% <p>Note: <code>Clause</code> must have type 50%% <code>clause</code>.</p> 51%% 52%% @see eval_guard/1 53%% @see any_catchall/1 54 55is_catchall(C) -> 56 case all_vars(clause_pats(C)) of 57 true -> 58 case eval_guard(clause_guard(C)) of 59 {value, true} -> 60 true; 61 _ -> 62 false 63 end; 64 false -> 65 false 66 end. 67 68all_vars([C | Cs]) -> 69 case is_c_var(C) of 70 true -> 71 all_vars(Cs); 72 false -> 73 false 74 end; 75all_vars([]) -> 76 true. 77 78 79%% @spec any_catchall(Clauses::[cerl()]) -> boolean() 80%% 81%% @doc Returns <code>true</code> if any of the abstract clauses in 82%% the list is a catch-all, otherwise <code>false</code>. See 83%% <code>is_catchall/1</code> for details. 84%% 85%% <p>Note: each node in <code>Clauses</code> must have type 86%% <code>clause</code>.</p> 87%% 88%% @see is_catchall/1 89 90any_catchall([C | Cs]) -> 91 case is_catchall(C) of 92 true -> 93 true; 94 false -> 95 any_catchall(Cs) 96 end; 97any_catchall([]) -> 98 false. 99 100 101%% @spec eval_guard(Expr::cerl()) -> none | {value, term()} 102%% 103%% @doc Tries to reduce a guard expression to a single constant value, 104%% if possible. The returned value is <code>{value, Term}</code> if the 105%% guard expression <code>Expr</code> always yields the constant value 106%% <code>Term</code>, and is otherwise <code>none</code>. 107%% 108%% <p>Note that although guard expressions should only yield boolean 109%% values, this function does not guarantee that <code>Term</code> is 110%% either <code>true</code> or <code>false</code>. Also note that only 111%% simple constructs like let-expressions are examined recursively; 112%% general constant folding is not performed.</p> 113%% 114%% @see is_catchall/1 115 116%% This function could possibly be improved further, but constant 117%% folding should in general be performed elsewhere. 118 119eval_guard(E) -> 120 case type(E) of 121 literal -> 122 {value, concrete(E)}; 123 values -> 124 case values_es(E) of 125 [E1] -> 126 eval_guard(E1); 127 _ -> 128 none 129 end; 130 'try' -> 131 eval_guard(try_arg(E)); 132 seq -> 133 eval_guard(seq_body(E)); 134 'let' -> 135 eval_guard(let_body(E)); 136 'letrec' -> 137 eval_guard(letrec_body(E)); 138 _ -> 139 none 140 end. 141 142 143%% --------------------------------------------------------------------- 144 145%% @spec reduce(Clauses) -> {true, {Clauses, Bindings}} 146%% | {false, Clauses} 147%% 148%% @equiv reduce(Cs, []) 149 150reduce(Cs) -> 151 reduce(Cs, []). 152 153%% @spec reduce(Clauses::[Clause], Exprs::[Expr]) -> 154%% {true, {Clause, Bindings}} 155%% | {false, [Clause]} 156%% 157%% Clause = cerl() 158%% Expr = any | cerl() 159%% Bindings = [{cerl(), cerl()}] 160%% 161%% @doc Selects a single clause, if possible, or otherwise reduces the 162%% list of selectable clauses. The input is a list <code>Clauses</code> 163%% of abstract clauses (i.e., syntax trees of type <code>clause</code>), 164%% and a list of switch expressions <code>Exprs</code>. The function 165%% tries to uniquely select a single clause or discard unselectable 166%% clauses, with respect to the switch expressions. All abstract clauses 167%% in the list must have the same number of patterns. If 168%% <code>Exprs</code> is not the empty list, it must have the same 169%% length as the number of patterns in each clause; see 170%% <code>match_list/2</code> for details. 171%% 172%% <p>A clause can only be selected if its guard expression always 173%% yields the atom <code>true</code>, and a clause whose guard 174%% expression always yields the atom <code>false</code> can never be 175%% selected. Other guard expressions are considered to have unknown 176%% value; cf. <code>eval_guard/1</code>.</p> 177%% 178%% <p>If a particular clause can be selected, the function returns 179%% <code>{true, {Clause, Bindings}}</code>, where <code>Clause</code> is 180%% the selected clause and <code>Bindings</code> is a list of pairs 181%% <code>{Var, SubExpr}</code> associating the variables occurring in 182%% the patterns of <code>Clause</code> with the corresponding 183%% subexpressions in <code>Exprs</code>. The list of bindings is given 184%% in innermost-first order; see the <code>match/2</code> function for 185%% details.</p> 186%% 187%% <p>If no clause could be definitely selected, the function returns 188%% <code>{false, NewClauses}</code>, where <code>NewClauses</code> is 189%% the list of entries in <code>Clauses</code> that remain after 190%% eliminating unselectable clauses, preserving the relative order.</p> 191%% 192%% @see eval_guard/1 193%% @see match/2 194%% @see match_list/2 195 196reduce(Cs, Es) -> 197 reduce(Cs, Es, []). 198 199reduce([C | Cs], Es, Cs1) -> 200 Ps = clause_pats(C), 201 case match_list(Ps, Es) of 202 none -> 203 %% Here, we know that the current clause cannot possibly be 204 %% selected, so we drop it and visit the rest. 205 reduce(Cs, Es, Cs1); 206 {false, _} -> 207 %% We are not sure if this clause might be selected, so we 208 %% save it and visit the rest. 209 reduce(Cs, Es, [C | Cs1]); 210 {true, Bs} -> 211 case eval_guard(clause_guard(C)) of 212 {value, true} when Cs1 == [] -> 213 %% We have a definite match - we return the residual 214 %% expression and signal that a selection has been 215 %% made. All other clauses are dropped. 216 {true, {C, Bs}}; 217 {value, true} -> 218 %% Unless one of the previous clauses is selected, 219 %% this clause will definitely be, so we can drop 220 %% the rest. 221 {false, reverse([C | Cs1])}; 222 {value, false} -> 223 %% This clause can never be selected, since its 224 %% guard is never 'true', so we drop it. 225 reduce(Cs, Es, Cs1); 226 _ -> 227 %% We are not sure if this clause might be selected 228 %% (or might even cause a crash), so we save it and 229 %% visit the rest. 230 reduce(Cs, Es, [C | Cs1]) 231 end 232 end; 233reduce([], _, Cs) -> 234 %% All clauses visited, without a complete match. Signal "not 235 %% reduced" and return the saved clauses, in the correct order. 236 {false, reverse(Cs)}. 237 238 239%% --------------------------------------------------------------------- 240 241%% @spec match(Pattern::cerl(), Expr) -> 242%% none | {true, Bindings} | {false, Bindings} 243%% 244%% Expr = any | cerl() 245%% Bindings = [{cerl(), Expr}] 246%% 247%% @doc Matches a pattern against an expression. The returned value is 248%% <code>none</code> if a match is impossible, <code>{true, 249%% Bindings}</code> if <code>Pattern</code> definitely matches 250%% <code>Expr</code>, and <code>{false, Bindings}</code> if a match is 251%% not definite, but cannot be excluded. <code>Bindings</code> is then 252%% a list of pairs <code>{Var, SubExpr}</code>, associating each 253%% variable in the pattern with either the corresponding subexpression 254%% of <code>Expr</code>, or with the atom <code>any</code> if no 255%% matching subexpression exists. (Recall that variables may not be 256%% repeated in a Core Erlang pattern.) The list of bindings is given 257%% in innermost-first order; this should only be of interest if 258%% <code>Pattern</code> contains one or more alias patterns. If the 259%% returned value is <code>{true, []}</code>, it implies that the 260%% pattern and the expression are syntactically identical. 261%% 262%% <p>Instead of a syntax tree, the atom <code>any</code> can be 263%% passed for <code>Expr</code> (or, more generally, be used for any 264%% subtree of <code>Expr</code>, in as much the abstract syntax tree 265%% implementation allows it); this means that it cannot be decided 266%% whether the pattern will match or not, and the corresponding 267%% variable bindings will all map to <code>any</code>. The typical use 268%% is for producing bindings for <code>receive</code> clauses.</p> 269%% 270%% <p>Note: Binary-syntax patterns are never structurally matched 271%% against binary-syntax expressions by this function.</p> 272%% 273%% <p>Examples: 274%% <ul> 275%% <li>Matching a pattern "<code>{X, Y}</code>" against the 276%% expression "<code>{foo, f(Z)}</code>" yields <code>{true, 277%% Bindings}</code> where <code>Bindings</code> associates 278%% "<code>X</code>" with the subtree "<code>foo</code>" and 279%% "<code>Y</code>" with the subtree "<code>f(Z)</code>".</li> 280%% 281%% <li>Matching pattern "<code>{X, {bar, Y}}</code>" against 282%% expression "<code>{foo, f(Z)}</code>" yields <code>{false, 283%% Bindings}</code> where <code>Bindings</code> associates 284%% "<code>X</code>" with the subtree "<code>foo</code>" and 285%% "<code>Y</code>" with <code>any</code> (because it is not known 286%% if "<code>{foo, Y}</code>" might match the run-time value of 287%% "<code>f(Z)</code>" or not).</li> 288%% 289%% <li>Matching pattern "<code>{foo, bar}</code>" against expression 290%% "<code>{foo, f()}</code>" yields <code>{false, []}</code>, 291%% telling us that there might be a match, but we cannot deduce any 292%% bindings.</li> 293%% 294%% <li>Matching <code>{foo, X = {bar, Y}}</code> against expression 295%% "<code>{foo, {bar, baz}}</code>" yields <code>{true, 296%% Bindings}</code> where <code>Bindings</code> associates 297%% "<code>Y</code>" with "<code>baz</code>", and "<code>X</code>" 298%% with "<code>{bar, baz}</code>".</li> 299%% 300%% <li>Matching a pattern "<code>{X, Y}</code>" against 301%% <code>any</code> yields <code>{false, Bindings}</code> where 302%% <code>Bindings</code> associates both "<code>X</code>" and 303%% "<code>Y</code>" with <code>any</code>.</li> 304%% </ul></p> 305 306match(P, E) -> 307 match(P, E, []). 308 309match(P, E, Bs) -> 310 case type(P) of 311 var -> 312 %% Variables always match, since they cannot have repeated 313 %% occurrences in a pattern. 314 {true, [{P, E} | Bs]}; 315 alias -> 316 %% All variables in P1 will be listed before the alias 317 %% variable in the result. 318 match(alias_pat(P), E, [{alias_var(P), E} | Bs]); 319 binary -> 320 %% The most we can do is to say "definitely no match" if a 321 %% binary pattern is matched against non-binary data. 322 if E == any -> 323 {false, Bs}; 324 true -> 325 case is_data(E) of 326 true -> 327 none; 328 false -> 329 {false, Bs} 330 end 331 end; 332 _ -> 333 match_1(P, E, Bs) 334 end. 335 336match_1(P, E, Bs) -> 337 case is_data(P) of 338 true when E == any -> 339 %% If we don't know the structure of the value of E at this 340 %% point, we just match the subpatterns against 'any', and 341 %% make sure the result is a "maybe". 342 Ps = data_es(P), 343 Es = lists:duplicate(length(Ps), any), 344 case match_list(Ps, Es, Bs) of 345 {_, Bs1} -> 346 {false, Bs1}; 347 none -> 348 none 349 end; 350 true -> 351 %% Test if the expression represents a constructor 352 case is_data(E) of 353 true -> 354 T1 = {data_type(E), data_arity(E)}, 355 T2 = {data_type(P), data_arity(P)}, 356 %% Note that we must test for exact equality. 357 if T1 =:= T2 -> 358 match_list(data_es(P), data_es(E), Bs); 359 true -> 360 none 361 end; 362 false -> 363 %% We don't know the run-time structure of E, and P 364 %% is not a variable or an alias pattern, so we 365 %% match against 'any' instead. 366 match_1(P, any, Bs) 367 end; 368 false -> 369 %% Strange pattern - give up, but don't say "no match". 370 {false, Bs} 371 end. 372 373 374%% @spec match_list(Patterns::[cerl()], Exprs::[Expr]) -> 375%% none | {true, Bindings} | {false, Bindings} 376%% 377%% Expr = any | cerl() 378%% Bindings = [{cerl(), cerl()}] 379%% 380%% @doc Like <code>match/2</code>, but matching a sequence of patterns 381%% against a sequence of expressions. Passing an empty list for 382%% <code>Exprs</code> is equivalent to passing a list of 383%% <code>any</code> atoms of the same length as <code>Patterns</code>. 384%% 385%% @see match/2 386 387match_list([], []) -> 388 {true, []}; % no patterns always match 389match_list(Ps, []) -> 390 match_list(Ps, lists:duplicate(length(Ps), any), []); 391match_list(Ps, Es) -> 392 match_list(Ps, Es, []). 393 394match_list([P | Ps], [E | Es], Bs) -> 395 case match(P, E, Bs) of 396 {true, Bs1} -> 397 match_list(Ps, Es, Bs1); 398 {false, Bs1} -> 399 %% Make sure "maybe" is preserved 400 case match_list(Ps, Es, Bs1) of 401 {_, Bs2} -> 402 {false, Bs2}; 403 none -> 404 none 405 end; 406 none -> 407 none 408 end; 409match_list([], [], Bs) -> 410 {true, Bs}. 411