% From a paper by G Canfora, Aniello Cimitile and Ugo de Carlini
% 'A Logic Based Approach to Reverse Engineering Tools Production'
% IEEE Trans SE18 n 2 Dec 1992, pages 1053-1063

% problem - record the structure of a complex program so that a programmer
% can ask questions about it when trying to create an improved version.
% This is for a Pascal program

% Utility rules used in other predicates
% non_member(E, X) is true if E is not in list X. 
%      it differs from `not member(E,X)` becuase if E is a variable the not
%      predicate backtracks and leaves E uninstanciated.
meta( non_member(e,l), 'Test if e is in list l').
non_member(_,[]).
non_member(E,[A|B]):-E\==A, non_member(E,B).

uniq([],[]).
uniq([H|T],[H|T2]):-non_member(H,T), !, uniq(T,T2).
uniq([H|T], T2):-uniq(T,T2).

meta( path_concat(p1,p2,p3), 'list p3 is/becomes list p1 in front of list p2').
path_concat([X], [X|Ys], [X|Ys]).
path_concat([X|Xs], Ys, [X|Zs]):-path_concat(Xs, Ys, Zs).

% basic predicates describe a particular program
% They are (ideally) extracted from code by a another program
basic(mod,1). basic(var_dec,2). basic(mod_dec,2). basic(par_dec,3).
basic(use,2). basic(set,2). basic(cal,2). basic(bind,4).
% notice that by including a definition of these predicates
% as part of the data base, we canwrite generic DataBase operations

clear_db:-basic(Atom,Arity), abolish(Atom,Arity),fail.
clear_db:- write('Program model erased'), nl.
list_db:-basic(Atom,Arity), write(Atom/Arity), nl, fail.
list_db.

% meta definitions document the meaning of predicates
meta( mod(x)  ,'x is a module.').
meta( var_dec(x,y)  ,'module x has declaration of variable called y').
meta( par_dec(x,y,i)  ,'module x has formal parameter y in position').
meta( mod_dec(x,y)  ,'module x has a declaration of a local module y').
meta( use(x,y)  ,'module x uses variable  y').
meta( set(x,y)  ,'module x sets the value of variable  y').
meta( cal(x,y)  ,'module x calls module y').
%ca not use 'call' since that indicates a call of a predicate.
meta( bind(x,y,z,i), 'Module x calls y and has z as actual parameter i').

%summary relations - questions a program may ask
meta( mod_dec_scope(m1,m2), 'Module m1 declares a module, that declares a module, ...that declares m2').
mod_dec_scope(M1,M2):-mod_dec(M1,M2).
mod_dec_scope(M1,M2):-mod_dec(M1,Mi), mod_dec_scope(Mi,M2).

meta( var_or_par_dec(m,i), 'Module m declares identifier i as a variable or parameter').
var_or_par_dec(M, VoP):-(var_dec(M,VoP); par_dec(M,(VoP,_))).

meta( visible(m1, (i,m2)), 'Identifier i declared in m2 is visible in m1').
visible(M,(VoP,M)):-mod(M), var_or_par_dec(M,VoP).
visible(M1,(VoP,M2)):-var_or_par_dec(M2,VoP),mod_dec_scope(M2,M1),
	not ( var_or_par_dec(M1,VoP); mod_dec_scope(M2,Mi),mod_dec_scope(Mi,M1),
			var_or_par_dec(Mi,VoP)
	).

meta( active(m1, m2,[m1,p,p,p|m2]), 'Paths for m1 to cal m2').
active(M,M,[M]):-mod(M).
active(M1,M2,[M1|Path]):-cal(M1,M3),active(M3,M2,Path).

meta( actualize(m1,i,(v,m2),p), 'module m1s ith parameter is actually identifier v declared or specified in m2, by path p').
actualize(M1,VoP,(VoP,M2), Path):-
	visible(M1, (VoP,M2)), var_dec(M2,VoP), active(main,M2,Path1),
	active(M2, M1, Path2),
	path_concat(Path1, Path2, Path).
actualize(M1,VoP,(Var,M2),Path):- visible(M1,(VoP,M3)),
	par_dec(M3,(VoP,Pos)),
	cal(M4,M3),
	bind(M4,M3,(VoP1,Pos)), active(M3,M1,Path1),
	actualize(M4,VoP1,(Var,M2),Path2),
	path_concat(Path2, [M4; Path1],Path).

meta( up_in((m1,p),(v,m2)), 'm1 is a module identified by path p and v is a variable in m2 that actually provides the data for m1 thru p').
up_in((M1,Path),(Var,M2)):- use(M1,VoP), actualize(M1,VoP,(Var,M2), Path), M2\==M1.
up_in((M1,Path),(Var,M2)):- cal(M1,M3), 
	active(main, M1,Path),
	path_concat(Path, [M1,M3], Path1),
	up_in((M3, Path1), (Var,M2)),
	M2\==M1.

% The next predicate needs 'set_of(V, P, V)' to work.
% meta( in_flow((m,p), v), 'Produces a set of input sets for (m,p) to module m thru pathp, from all other modules').
in_flow((M, Path), VarSet):- active(main,M,Path), set_of(VarSet, up_in((M,Path), VarSet), VarSet).

% user interfaces
declarations:-mod(M),declared(M),fail.
declarations.
declared(M):-var_dec(M,V), write(M), write(' declares variable '),  write(V), nl.
declared(M):-par_dec(M,(V,_)), write(M), write(' has parameter '),  write(V), nl.
declared(M):-mod_dec(M,V), write(M), write(' declares module '),  write(V), nl.
calls:-mod(M),calls(M),fail.
calls.
calls(M):-cal(M,M2), write(M), write(' calls '),  write(M2), nl.

usage:-mod(M),uses(M),fail.
usage.
uses(M):-use(M,V), write(M), write(' uses '),  write(V), nl.
uses(M):-set(M,V), write(M), write(' sets '),  write(V), nl.

list:-declarations, calls, usage.
%...
% sample data
mod(main).
var_dec(main,x). var_dec(main,y). mod_dec(main,a). mod_dec(main, d).
cal(main, a). bind(main, a, (x,1)). bind(main, a, (y,2)).
cal(main,d).
use(main,x). use(main,y).

mod(a).
var_dec(a,l). var_dec(a,m). par_dec(a, (t,1)). par_dec(a, (z,2)).
mod_dec(a,b).
mod_dec(a,c).
cal(a,b). bind(a,b,(t,1)). bind(a,b,(m,2)).
cal(a,c). bind(a,c,(m,1)). bind(a,c,(l,1)).  % two different calls to c in a

mod(b). var_dec(b,u). par_dec(b, (x,1)). par_dec(b, (z,2)).
use(b,x). use(b,z). use(b,l). use(b,u).

mod(c).  var_dec(c,p). par_dec(c, (q,1)).
cal(c,b).  bind(c,b,(q,1)). bind(c,b,(p,1)). bind(c,b,(x,2)). bind(c,b,(t,2)).
set(c,p).
use(c,q).

mod(d).
var_dec(d,r). var_dec(d,s).
cal(d,a).
bind(d,a,(r,1)). bind(d,a,(s,1)). bind(d,a, (y,2)).
use(d,x).