erl_syntax_lib.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 1,970 行 · 第 1/5 页

%% =====================================================================
%% This library is free software; you can redistribute it and/or modify
%% it under the terms of the GNU Lesser General Public License as
%% published by the Free Software Foundation; either version 2 of the
%% License, or (at your option) any later version.
%%
%% This library is distributed in the hope that it will be useful, but
%% WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
%% Lesser General Public License for more details.
%%
%% You should have received a copy of the GNU Lesser General Public
%% License along with this library; if not, write to the Free Software
%% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
%% USA
%%
%% $Id$
%%
%% @copyright 1997-2006 Richard Carlsson
%% @author Richard Carlsson <[e-mail]>
%% @end
%% =====================================================================

%% @doc Support library for abstract Erlang syntax trees.
%%
%% This module contains utility functions for working with the
%% abstract data type defined in the module {@link erl_syntax}.
%%
%% @type syntaxTree() = erl_syntax:syntaxTree(). An abstract syntax
%% tree. See the {@link erl_syntax} module for details.

-module(erl_syntax_lib).

-export([analyze_application/1, analyze_attribute/1,
         analyze_export_attribute/1, analyze_file_attribute/1,
         analyze_form/1, analyze_forms/1, analyze_function/1,
         analyze_function_name/1, analyze_implicit_fun/1,
         analyze_import_attribute/1, analyze_module_attribute/1,
         analyze_record_attribute/1, analyze_record_expr/1,
         analyze_record_field/1, analyze_rule/1,
         analyze_wild_attribute/1, annotate_bindings/1,
         annotate_bindings/2, fold/3, fold_subtrees/3, foldl_listlist/3,
         function_name_expansions/1, is_fail_expr/1, limit/2, limit/3,
         map/2, map_subtrees/2, mapfold/3, mapfold_subtrees/3,
         mapfoldl_listlist/3, new_variable_name/1, new_variable_name/2,
         new_variable_names/2, new_variable_names/3, strip_comments/1,
         to_comment/1, to_comment/2, to_comment/3, variables/1]).


%% =====================================================================
%% @spec map(Function, Tree::syntaxTree()) -> syntaxTree()
%%
%%          Function = (syntaxTree()) -> syntaxTree()
%% 
%% @doc Applies a function to each node of a syntax tree. The result of
%% each application replaces the corresponding original node. The order
%% of traversal is bottom-up.
%%
%% @see map_subtrees/2

map(F, Tree) ->
    case erl_syntax:subtrees(Tree) of
        [] ->
            F(Tree);
        Gs ->
            Tree1 = erl_syntax:make_tree(erl_syntax:type(Tree),
                                         [[map(F, T) || T <- G]
                                          || G <- Gs]),
            F(erl_syntax:copy_attrs(Tree, Tree1))
    end.


%% =====================================================================
%% @spec map_subtrees(Function, syntaxTree()) -> syntaxTree()
%%
%%          Function = (Tree) -> Tree1
%%         
%% @doc Applies a function to each immediate subtree of a syntax tree.
%% The result of each application replaces the corresponding original
%% node.
%%
%% @see map/2

map_subtrees(F, Tree) ->
    case erl_syntax:subtrees(Tree) of
        [] ->
            Tree;
        Gs ->
            Tree1 = erl_syntax:make_tree(erl_syntax:type(Tree),
                                         [[F(T) || T <- G] || G <- Gs]),
            erl_syntax:copy_attrs(Tree, Tree1)
    end.


%% =====================================================================
%% @spec fold(Function, Start::term(), Tree::syntaxTree()) -> term()
%%
%%          Function = (syntaxTree(), term()) -> term()
%%
%% @doc Folds a function over all nodes of a syntax tree. The result is
%% the value of `Function(X1, Function(X2, ... Function(Xn, Start)
%% ... ))', where `[X1, X2, ..., Xn]' are the nodes of
%% `Tree' in a post-order traversal.
%%
%% @see fold_subtrees/3
%% @see foldl_listlist/3

fold(F, S, Tree) ->
    case erl_syntax:subtrees(Tree) of
        [] ->
            F(Tree, S);
        Gs ->
            F(Tree, fold_1(F, S, Gs))
    end.

fold_1(F, S, [L | Ls]) ->
    fold_1(F, fold_2(F, S, L), Ls);
fold_1(_, S, []) ->
    S.

fold_2(F, S, [T | Ts]) ->
    fold_2(F, fold(F, S, T), Ts);
fold_2(_, S, []) ->
    S.


%% =====================================================================
%% @spec fold_subtrees(Function, Start::term(), Tree::syntaxTree()) ->
%%           term()
%%
%%          Function = (syntaxTree(), term()) -> term()
%%
%% @doc Folds a function over the immediate subtrees of a syntax tree.
%% This is similar to `fold/3', but only on the immediate
%% subtrees of `Tree', in left-to-right order; it does not
%% include the root node of `Tree'.
%%
%% @see fold/3

fold_subtrees(F, S, Tree) ->
    foldl_listlist(F, S, erl_syntax:subtrees(Tree)).


%% =====================================================================
%% @spec foldl_listlist(Function, Start::term(), [[term()]]) -> term()
%%
%%          Function = (term(), term()) -> term()
%%
%% @doc Like `lists:foldl/3', but over a list of lists.
%%
%% @see fold/3
%% @see //stdlib/lists:foldl/3

foldl_listlist(F, S, [L | Ls]) ->
    foldl_listlist(F, foldl(F, S, L), Ls);
foldl_listlist(_, S, []) ->
    S.

foldl(F, S, [T | Ts]) ->
    foldl(F, F(T, S), Ts);
foldl(_, S, []) ->
    S.


%% =====================================================================
%% @spec mapfold(Function, Start::term(), Tree::syntaxTree()) ->
%%           {syntaxTree(), term()}
%%
%%          Function = (syntaxTree(), term()) -> {syntaxTree(), term()}
%%
%% @doc Combines map and fold in a single operation. This is similar to
%% `map/2', but also propagates an extra value from each
%% application of the `Function' to the next, while doing a
%% post-order traversal of the tree like `fold/3'. The value
%% `Start' is passed to the first function application, and
%% the final result is the result of the last application.
%%
%% @see map/2
%% @see fold/3

mapfold(F, S, Tree) ->
    case erl_syntax:subtrees(Tree) of
        [] ->
            F(Tree, S);
        Gs ->
            {Gs1, S1} = mapfold_1(F, S, Gs),
            Tree1 = erl_syntax:make_tree(erl_syntax:type(Tree), Gs1),
            F(erl_syntax:copy_attrs(Tree, Tree1), S1)
    end.

mapfold_1(F, S, [L | Ls]) ->
    {L1, S1} = mapfold_2(F, S, L),
    {Ls1, S2} = mapfold_1(F, S1, Ls),
    {[L1 | Ls1], S2};
mapfold_1(_, S, []) ->
    {[], S}.

mapfold_2(F, S, [T | Ts]) ->
    {T1, S1} = mapfold(F, S, T),
    {Ts1, S2} = mapfold_2(F, S1, Ts),
    {[T1 | Ts1], S2};
mapfold_2(_, S, []) ->
    {[], S}.


%% =====================================================================
%% @spec mapfold_subtrees(Function, Start::term(),
%%                        Tree::syntaxTree()) -> {syntaxTree(), term()}
%%
%%          Function = (syntaxTree(), term()) -> {syntaxTree(), term()}
%%
%% @doc Does a mapfold operation over the immediate subtrees of a syntax
%% tree. This is similar to `mapfold/3', but only on the
%% immediate subtrees of `Tree', in left-to-right order; it
%% does not include the root node of `Tree'.
%%
%% @see mapfold/3

mapfold_subtrees(F, S, Tree) ->
    case erl_syntax:subtrees(Tree) of
        [] ->
            {Tree, S};
        Gs ->
            {Gs1, S1} = mapfoldl_listlist(F, S, Gs),
            Tree1 = erl_syntax:make_tree(erl_syntax:type(Tree), Gs1),
            {erl_syntax:copy_attrs(Tree, Tree1), S1}
    end.


%% =====================================================================
%% @spec mapfoldl_listlist(Function, State, [[term()]]) ->
%%           {[[term()]], term()}
%%
%%          Function = (term(), term()) -> {term(), term()}
%%
%% @doc Like `lists:mapfoldl/3', but over a list of lists.
%% The list of lists in the result has the same structure as the given
%% list of lists.

mapfoldl_listlist(F, S, [L | Ls]) ->
    {L1, S1} = mapfoldl(F, S, L),
    {Ls1, S2} = mapfoldl_listlist(F, S1, Ls),
    {[L1 | Ls1], S2};
mapfoldl_listlist(_, S, []) ->
    {[], S}.

mapfoldl(F, S, [L | Ls]) ->
    {L1, S1} = F(L, S),
    {Ls1, S2} = mapfoldl(F, S1, Ls),
    {[L1 | Ls1], S2};
mapfoldl(_, S, []) ->
    {[], S}.


%% =====================================================================
%% @spec variables(syntaxTree()) -> set(atom())
%%
%%        set(T) = //stdlib/sets:set(T)
%%
%% @doc Returns the names of variables occurring in a syntax tree, The
%% result is a set of variable names represented by atoms. Macro names
%% are not included.
%%
%% @see //stdlib/sets

variables(Tree) ->
    variables(Tree, sets:new()).

variables(T, S) ->
    case erl_syntax:type(T) of
	variable ->
	    sets:add_element(erl_syntax:variable_name(T), S);
	macro ->
	    %% macro names are ignored, even if represented by variables
	    case erl_syntax:macro_arguments(T) of
		none -> S;
		As ->
		    variables_2(As, S)
	    end;
	_ ->
	    case erl_syntax:subtrees(T) of
		[] ->
		    S;
		Gs ->
		    variables_1(Gs, S)
	    end
    end.

variables_1([L | Ls], S) ->
    variables_1(Ls, variables_2(L, S));
variables_1([], S) ->
    S.

variables_2([T | Ts], S) ->
    variables_2(Ts, variables(T, S));
variables_2([], S) ->
    S.


-define(MINIMUM_RANGE, 100).
-define(START_RANGE_FACTOR, 100).
-define(MAX_RETRIES, 3).    % retries before enlarging range
-define(ENLARGE_ENUM, 8).   % range enlargment enumerator
-define(ENLARGE_DENOM, 1).  % range enlargment denominator

default_variable_name(N) ->
    list_to_atom("V" ++ integer_to_list(N)).

%% =====================================================================
%% @spec new_variable_name(Used::set(atom())) -> atom()
%%
%% @doc Returns an atom which is not already in the set `Used'. This is
%% equivalent to `new_variable_name(Function, Used)', where `Function'
%% maps a given integer `N' to the atom whose name consists of "`V'"
%% followed by the numeral for `N'.
%%
%% @see new_variable_name/2

new_variable_name(S) ->
    new_variable_name(fun default_variable_name/1, S).

%% =====================================================================
%% @spec new_variable_name(Function, Used::set(atom())) -> atom()
%%
%%          Function = (integer()) -> atom()
%%
%% @doc Returns a user-named atom which is not already in the set
%% `Used'. The atom is generated by applying the given
%% `Function' to a generated integer. Integers are generated
%% using an algorithm which tries to keep the names randomly distributed
%% within a reasonably small range relative to the number of elements in
%% the set.
%%
%% This function uses the module `random' to generate new
%% keys. The seed it uses may be initialized by calling
%% `random:seed/0' or `random:seed/3' before this
%% function is first called.
%%
%% @see new_variable_name/1
%% @see //stdlib/sets
%% @see //stdlib/random

new_variable_name(F, S) ->
    R = start_range(S),
    new_variable_name(R, F, S).

new_variable_name(R, F, S) ->
    new_variable_name(generate(R, R), R, 0, F, S).

new_variable_name(N, R, T, F, S) when T < ?MAX_RETRIES ->
    A = F(N),
    case sets:is_element(A, S) of
        true ->
            new_variable_name(generate(N, R), R, T + 1, F, S);
        false ->
            A
    end;
new_variable_name(N, R, _T, F, S) ->
    %% Too many retries - enlarge the range and start over.
    R1 = (R * ?ENLARGE_ENUM) div ?ENLARGE_DENOM,
    new_variable_name(generate(N, R1), R1, 0, F, S).

%% Note that we assume that it is very cheap to take the size of
%% the given set. This should be valid for the stdlib
%% implementation of `sets'.

start_range(S) ->
    max(sets:size(S) * ?START_RANGE_FACTOR, ?MINIMUM_RANGE).

max(X, Y) when X > Y -> X;
max(_, Y) -> Y.

%% The previous number might or might not be used to compute the
%% next number to be tried. It is currently not used.
%%
%% It is important that this function does not generate values in
%% order, but (pseudo-)randomly distributed over the range.

generate(_Key, Range) ->
    random:uniform(Range).    % works well


%% =====================================================================
%% @spec new_variable_names(N::integer(), Used::set(atom())) -> [atom()]
%%
%% @doc Like `new_variable_name/1', but generates a list of
%% `N' new names.
%% 
%% @see new_variable_name/1

new_variable_names(N, S) ->
    new_variable_names(N, fun default_variable_name/1, S).

%% =====================================================================