1/*  Part of SWI-Prolog
    2
    3    Author:        Eva Stoewe, Guenter Kniesel and Jan Wielemaker
    4    E-mail:        pdt@lists.iai.uni-bonn.de
    5    WWW:           http://sewiki.iai.uni-bonn.de/research/pdt/start
    6    Copyright (c)  2004-2012, CS Dept. III, University of Bonn
    7    All rights reserved.
    8
    9    Redistribution and use in source and binary forms, with or without
   10    modification, are permitted provided that the following conditions
   11    are met:
   12
   13    1. Redistributions of source code must retain the above copyright
   14       notice, this list of conditions and the following disclaimer.
   15
   16    2. Redistributions in binary form must reproduce the above copyright
   17       notice, this list of conditions and the following disclaimer in
   18       the documentation and/or other materials provided with the
   19       distribution.
   20
   21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   25    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   29    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   31    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   32    POSSIBILITY OF SUCH DAMAGE.
   33*/
   34
   35:- module(prolog_metainference,
   36          [ infer_meta_predicate/2,             % :Head, -MetaSpec
   37            inferred_meta_predicate/2           % :Head, ?MetaSpec
   38          ]).   39:- use_module(library(lists)).   40:- use_module(library(apply)).   41
   42:- meta_predicate
   43    inferred_meta_predicate(:, ?),
   44    infer_meta_predicate(:, -).   45
   46:- dynamic
   47    inferred_meta_pred/3.                   % Head, Module, Meta
   48
   49/** <module> Infer meta-predicate properties
   50
   51This module infers meta-predicate properties   by inspecting the clauses
   52of predicates that call other predicates.   This is extremely useful for
   53program analysis and refactoring because  many   programs  `in the wild'
   54have incomplete or incorrect meta-predicate information.
   55
   56@see    This library is used by prolog_walk_code/1 to improve the
   57        accuracy of this analysis.
   58@tbd    Re-introduce some alias-analysis
   59@tbd    Not all missing meta-declarations are interesting.  Notably,
   60        meta-predicates that are private and only pass meta-arguments
   61        on behalve of a public meta-predicates do not need a declaration.
   62*/
   63
   64
   65%!  inferred_meta_predicate(:Head, ?MetaSpec) is nondet.
   66%
   67%   True when MetaSpec is an   inferred meta-predicate specification
   68%   for Head.
   69
   70inferred_meta_predicate(M:Head, MetaSpec) :-
   71    inferred_meta_pred(Head, M, MetaSpec).
   72inferred_meta_predicate(M:Head, MetaSpec) :-
   73    predicate_property(M:Head, imported_from(From)),
   74    inferred_meta_pred(Head, From, MetaSpec).
   75
   76
   77%!  infer_meta_predicate(:Head, -MetaSpec) is semidet
   78%
   79%   True  when  MetaSpec  is  a  meta-predicate  specifier  for  the
   80%   predicate Head. Derived meta-predicates are   collected and made
   81%   available through inferred_meta_predicate/2.
   82
   83infer_meta_predicate(Head, MetaSpec) :-
   84    inferred_meta_predicate(Head, MetaSpec),
   85    !.
   86infer_meta_predicate(M:Head, MetaSpec) :-
   87    predicate_property(M:Head, imported_from(From)),
   88    !,
   89    do_infer_meta_predicate(From:Head, MetaSpec),
   90    assertz(inferred_meta_pred(Head, From, MetaSpec)).
   91infer_meta_predicate(M:Head, MetaSpec) :-
   92    do_infer_meta_predicate(M:Head, MetaSpec),
   93    assertz(inferred_meta_pred(Head, M, MetaSpec)).
   94
   95:- meta_predicate
   96    do_infer_meta_predicate(:, -).   97
   98do_infer_meta_predicate(Module:AHead, MetaSpec):-
   99    functor(AHead, Functor, Arity),
  100    functor(Head, Functor, Arity),  % Generalise the head
  101    findall(MetaSpec,
  102            meta_pred_args_in_clause(Module, Head, MetaSpec),
  103            MetaSpecs),
  104    MetaSpecs \== [],
  105    combine_meta_args(MetaSpecs, MetaSpec).
  106
  107
  108%!  meta_pred_args_in_clause(+Module, +Head, -MetaSpec) is nondet.
  109
  110meta_pred_args_in_clause(Module, Head, MetaArgs) :-
  111    clause(Module:Head, Body),
  112    annotate_meta_vars_in_body(Body, Module),
  113    meta_annotation(Head, MetaArgs).
  114
  115
  116%!  annotate_meta_vars_in_body(+Term, +Module) is det
  117%
  118%   Annotate variables in Term if they appear as meta-arguments.
  119%
  120%   @tbd    Aliasing.  Previous code detected aliasing for
  121%           - =/2
  122%           - functor/3
  123%           - atom_concat/3
  124%           - =../2
  125%           - arg/3
  126%   @tbd    We can make this nondet, exploring multiple aliasing
  127%           paths in disjunctions.
  128
  129annotate_meta_vars_in_body(A, _) :-
  130    atomic(A),
  131    !.
  132annotate_meta_vars_in_body(Var, _) :-
  133    var(Var),
  134    !,
  135    annotate(Var, 0).
  136annotate_meta_vars_in_body(Module:Term, _) :-
  137    !,
  138    (   atom(Module)
  139    ->  annotate_meta_vars_in_body(Term, Module)
  140    ;   var(Module)
  141    ->  annotate(Module, m)
  142    ;   true                        % may continue if Term is a system
  143    ).                              % predicate?
  144annotate_meta_vars_in_body((TermA, TermB), Module) :-
  145    !,
  146    annotate_meta_vars_in_body(TermB, Module),
  147    annotate_meta_vars_in_body(TermA, Module).
  148annotate_meta_vars_in_body((TermA; TermB), Module) :-
  149    !,
  150    annotate_meta_vars_in_body(TermB, Module),
  151    annotate_meta_vars_in_body(TermA, Module).
  152annotate_meta_vars_in_body((TermA->TermB), Module) :-
  153    !,
  154    annotate_meta_vars_in_body(TermB, Module),
  155    annotate_meta_vars_in_body(TermA, Module).
  156annotate_meta_vars_in_body((TermA*->TermB), Module) :-
  157    !,
  158    annotate_meta_vars_in_body(TermB, Module),
  159    annotate_meta_vars_in_body(TermA, Module).
  160annotate_meta_vars_in_body(A=B, _) :-
  161    var(A), var(B),
  162    !,
  163    A = B.
  164annotate_meta_vars_in_body(Goal, Module) :- % TBD: do we trust this?
  165    predicate_property(Module:Goal, meta_predicate(Head)),
  166    !,
  167    functor(Goal, _, Arity),
  168    annotate_meta_args(1, Arity, Goal, Head, Module).
  169annotate_meta_vars_in_body(Goal, Module) :-
  170    inferred_meta_predicate(Module:Goal, Head),
  171    !,
  172    functor(Goal, _, Arity),
  173    annotate_meta_args(1, Arity, Goal, Head, Module).
  174annotate_meta_vars_in_body(_, _).
  175
  176
  177%!  annotate_meta_args(+Arg, +Arity, +Goal, +MetaSpec, +Module)
  178
  179annotate_meta_args(I, Arity, Goal, MetaSpec, Module) :-
  180    I =< Arity,
  181    !,
  182    arg(I, MetaSpec, MetaArg),
  183    arg(I, Goal, Arg),
  184    annotate_meta_arg(MetaArg, Arg, Module),
  185    I2 is I + 1,
  186    annotate_meta_args(I2, Arity, Goal, MetaSpec, Module).
  187annotate_meta_args(_, _, _, _, _).
  188
  189annotate_meta_arg(Spec, Arg, _) :-
  190    var(Arg),
  191    !,
  192    annotate(Arg, Spec).
  193annotate_meta_arg(0, Arg, Module) :-
  194    !,
  195    annotate_meta_vars_in_body(Arg, Module).
  196annotate_meta_arg(N, Arg, Module) :-
  197    integer(N),
  198    callable(Arg),
  199    !,
  200    Arg =.. List,
  201    length(Extra, N),
  202    append(List, Extra, ListX),
  203    ArgX =.. ListX,
  204    annotate_meta_vars_in_body(ArgX, Module).
  205annotate_meta_arg(Spec, Arg, _) :-
  206    is_meta(Spec),
  207    compound(Arg),
  208    Arg = Module:_,
  209    var(Module),
  210    !,
  211    annotate(Module, m).
  212annotate_meta_arg(_,_,_).
  213
  214annotate(Var, Annotation) :-
  215    get_attr(Var, prolog_metainference, Annot0),
  216    !,
  217    join_annotation(Annot0, Annotation, Joined),
  218    put_attr(Var, prolog_metainference, Joined).
  219annotate(Var, Annotation) :-
  220    put_attr(Var, prolog_metainference, Annotation).
  221
  222join_annotation(A, A, A) :- !.
  223join_annotation(A, B, C) :-
  224    (   is_meta(A), \+ is_meta(B)
  225    ->  C = A
  226    ;   \+ is_meta(A), is_meta(B)
  227    ->  C = B
  228    ;   is_meta(A), is_meta(B)
  229    ->  C = (:)
  230    ;   C = *
  231    ).
  232
  233attr_unify_hook(A0, Other) :-
  234    get_attr(Other, prolog_metainference, A1),
  235    !,
  236    join_annotation(A0, A1, A),
  237    put_attr(Other, prolog_metainference, A).
  238
  239
  240%!  meta_annotation(+Head, -Annotation) is semidet.
  241%
  242%   True when Annotation is an   appropriate  meta-specification for
  243%   Head.
  244
  245meta_annotation(Head, Meta) :-
  246    functor(Head, Name, Arity),
  247    functor(Meta, Name, Arity),
  248    meta_args(1, Arity, Head, Meta, HasMeta),
  249    HasMeta == true.
  250
  251meta_args(I, Arity, Head, Meta, HasMeta) :-
  252    I =< Arity,
  253    !,
  254    arg(I, Head, HeadArg),
  255    arg(I, Meta, MetaArg),
  256    meta_arg(HeadArg, MetaArg),
  257    (   is_meta(MetaArg)
  258    ->  HasMeta = true
  259    ;   true
  260    ),
  261    I2 is I + 1,
  262    meta_args(I2, Arity, Head, Meta, HasMeta).
  263meta_args(_, _, _, _, _).
  264
  265is_meta(I) :- integer(I), !.
  266is_meta(:).
  267is_meta(^).
  268is_meta(//).
  269
  270%!  meta_arg(+AnnotatedArg, -MetaSpec) is det.
  271%
  272%   True when MetaSpec is  a  proper   annotation  for  the argument
  273%   AnnotatedArg. This is simple if the argument is a plain argument
  274%   in the head (first clause). If it   is  a compound term, it must
  275%   unify to _:_, otherwise there is no point turning it into a meta
  276%   argument. If the  module  part  is   then  passed  to  a  module
  277%   sensitive predicate, we assume it is a meta-predicate.
  278
  279meta_arg(HeadArg, MetaArg) :-
  280    get_attr(HeadArg, prolog_metainference, MetaArg),
  281    MetaArg \== m,
  282    !.
  283meta_arg(HeadArg, :) :-
  284    compound(HeadArg),
  285    HeadArg = M:_,
  286    get_attr(M, prolog_metainference, m),
  287    !.
  288meta_arg(_, *).
  289
  290%!  combine_meta_args(+Heads, -Head) is det.
  291%
  292%   Combine multiple meta-specifications.
  293
  294combine_meta_args([], []) :- !.
  295combine_meta_args([List], List) :- !.
  296combine_meta_args([Spec,Spec|Specs], CombinedArgs) :-
  297    !,
  298    combine_meta_args([Spec|Specs], CombinedArgs).
  299combine_meta_args([Spec1,Spec2|Specs], CombinedArgs) :-
  300    Spec1 =.. [Name|Args1],
  301    Spec2 =.. [Name|Args2],
  302    maplist(join_annotation, Args1, Args2, Args),
  303    Spec =.. [Name|Args],
  304    combine_meta_args([Spec|Specs], CombinedArgs)