[m-rev.] diff: clean up term_traversal.m
Julien Fischer
juliensf at cs.mu.OZ.AU
Tue Aug 16 01:27:51 AEST 2005
Estimated hours taken: 0.2
Branches: main
compiler/term_traversal.m:
Shift to 4-space indentation throughout.
Use '.' as a module qualifier throughout; previously
we only used it some places.
s/map(prog_var, (type))/vartypes/
Improve the comment about why pass 1 traverses negated goals.
The existing comment gives the impression that this is optional;
it isn't, because pass 1 is also responsible for detecting calls
to non-terminating procedures and pass 2 relies on this having been
done.
Other minor formatting changes, e.g. positioning of comments etc.
Julien.
Index: term_traversal.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/term_traversal.m,v
retrieving revision 1.36
diff -u -b -r1.36 term_traversal.m
--- term_traversal.m 12 Aug 2005 05:14:15 -0000 1.36
+++ term_traversal.m 15 Aug 2005 15:13:09 -0000
@@ -1,4 +1,6 @@
%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
% Copyright (C) 1997-2005 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
@@ -16,66 +18,65 @@
%
%-----------------------------------------------------------------------------%
-:- module transform_hlds__term_traversal.
+:- module transform_hlds.term_traversal.
:- interface.
-:- import_module hlds__hlds_goal.
-:- import_module hlds__hlds_module.
-:- import_module hlds__hlds_pred.
-:- import_module parse_tree__prog_data.
-:- import_module transform_hlds__term_errors.
-:- import_module transform_hlds__term_norm.
-:- import_module transform_hlds__term_util.
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_module.
+:- import_module hlds.hlds_pred.
+:- import_module parse_tree.prog_data.
+:- import_module transform_hlds.term_errors.
+:- import_module transform_hlds.term_norm.
+:- import_module transform_hlds.term_util.
:- import_module bag.
:- import_module list.
-:- import_module map.
:- import_module set.
:- import_module std_util.
+%-----------------------------------------------------------------------------%
+
:- type traversal_info
---> ok(
set(path_info),
- % Information about the paths we have
- % followed. With a conjunction of
- % length N, each of whose elements is
- % a branched control structure, the
- % number of paths through the
- % conjunction is 2^N. The reason why
- % we use a set of path_infos instead
- % of a list is that this can postpone
- % the representation getting too big
- % if (as is at least moderately likely)
- % many of the paths have identical
+ % Information about the paths we have followed. With
+ % a conjunction of length N, each of whose elements
+ % is a branched control structure, the number of
+ % paths through the conjunction is 2^N. The reason
+ % why we use a set of path_infos instead of a list
+ % is that this can postpone the representation
+ % getting too big if (as is at least moderately
+ % likely) many of the paths have identical
% properties.
- list(term_errors__error)
- % Have we processed a call to a
- % procedure whose maybe termination
- % info was yes(can_loop(_))?
- % If yes, record the error here.
- % (This is not an error in pass 1,
- % but we want to find this out in
- % pass 1 so we can avoid doing pass 2.)
+
+ list(term_errors.error)
+ % Have we processed a call to a procedure whose
+ % maybe termination info was yes(can_loop(_))? If
+ % yes, record the error here. (This is not an error
+ % in pass 1, but we want to find this out in pass 1
+ % so we can avoid doing pass 2.)
)
- ; error(
- list(term_errors__error),
- % Errors which are fatal in both
- % passes.
- list(term_errors__error)
- % Have we processed a call to a
- % procedure whose maybe termination
- % info was yes(can_loop(_))?
- % If yes, record the error here.
- % (This is not an error in pass 1,
- % but we want to find this out in
- % pass 1 so we can avoid doing pass 2.)
+ ;
+ error(
+ list(term_errors.error),
+ % Errors which are fatal in both % passes.
+
+ list(term_errors.error)
+ % Have we processed a call to a procedure whose
+ % maybe termination info was yes(can_loop(_))? If
+ % yes, record the error here. (This is not an error
+ % in pass 1, but we want to find this out in pass 1
+ % so we can avoid doing pass 2.)
).
:- type path_info
---> path_info(
- pred_proc_id, % The identify of the procedure
+
+ pred_proc_id,
+ % The identify of the procedure
% that this path is within.
+
maybe(pair(pred_proc_id, prog_context)),
% If no, path was started at the end
% of the procedure given by field 1.
@@ -84,18 +85,18 @@
% and the context of the call.
% In pass 1, all starts should be no.
% In pass 2, all starts should be yes.
+
int,
list(pred_proc_id),
bag(prog_var)
- % These three fields describe the
- % right hand side of the inequation
- % we are propagating.
+ % These three fields describe the right hand side
+ % of the inequation we are propagating.
).
:- type traversal_params.
:- pred init_traversal_params(module_info::in, functor_info::in,
- pred_proc_id::in, prog_context::in, map(prog_var, type)::in,
+ pred_proc_id::in, prog_context::in, vartypes::in,
used_args::in, used_args::in, int::in, int::in,
traversal_params::out) is det.
@@ -109,16 +110,20 @@
:- implementation.
-:- import_module check_hlds__type_util.
-:- import_module hlds__hlds_data.
-:- import_module parse_tree__error_util.
-:- import_module parse_tree__prog_type.
+:- import_module check_hlds.type_util.
+:- import_module hlds.hlds_data.
+:- import_module parse_tree.error_util.
+:- import_module parse_tree.prog_type.
:- import_module assoc_list.
:- import_module bool.
:- import_module int.
+:- import_module map.
:- import_module require.
:- import_module string.
+:- import_module svset.
+
+%-----------------------------------------------------------------------------%
traverse_goal(Goal, Params, !Info) :-
Goal = GoalExpr - GoalInfo,
@@ -143,7 +148,7 @@
unify_change(OutVar, ConsId, Args, Modes, Params,
Gamma, InVars, OutVars0)
->
- bag__insert(OutVars0, OutVar, OutVars),
+ bag.insert(OutVars0, OutVar, OutVars),
record_change(InVars, OutVars, Gamma, [], !Info)
;
% length(Args) is not necessarily equal to length(Modes)
@@ -156,7 +161,7 @@
unify_change(InVar, ConsId, Args, Modes, Params,
Gamma0, InVars0, OutVars)
->
- bag__insert(InVars0, InVar, InVars),
+ bag.insert(InVars0, InVar, InVars),
Gamma = 0 - Gamma0,
record_change(InVars, OutVars, Gamma, [], !Info)
;
@@ -165,9 +170,9 @@
)
;
Unification = assign(OutVar, InVar),
- bag__init(Empty),
- bag__insert(Empty, InVar, InVars),
- bag__insert(Empty, OutVar, OutVars),
+ bag.init(Empty),
+ bag.insert(Empty, InVar, InVars),
+ bag.insert(Empty, OutVar, OutVars),
record_change(InVars, OutVars, 0, [], !Info)
;
Unification = simple_test(_InVar1, _InVar2)
@@ -177,11 +182,11 @@
).
traverse_goal_2(conj(Goals), _, Params, !Info) :-
- list__reverse(Goals, RevGoals),
+ list.reverse(Goals, RevGoals),
traverse_conj(RevGoals, Params, !Info).
traverse_goal_2(par_conj(Goals), _, Params, !Info) :-
- list__reverse(Goals, RevGoals),
+ list.reverse(Goals, RevGoals),
traverse_conj(RevGoals, Params, !Info).
traverse_goal_2(switch(_, _, Cases), _, Params, !Info) :-
@@ -191,9 +196,11 @@
traverse_disj(Goals, Params, !Info).
traverse_goal_2(not(Goal), _, Params, !Info) :-
- % Since goal cannot bind any active variables,
- % we don't need to traverse Goal for pass1,
- % but it shouldn't hurt either.
+ % The negated goal will not affect the argument sizes since it
+ % cannot bind any active variables. However, we must traverse
+ % it anyway during pass 1 to ensure that it does not call any
+ % non-terminating procedures. Pass 2 relies on pass 1 having
+ % done this.
traverse_goal(Goal, Params, !Info).
traverse_goal_2(scope(_, Goal), _GoalInfo, Params, !Info) :-
@@ -210,20 +217,17 @@
module_info_pred_proc_info(Module, CallPredId, CallProcId, _,
CallProcInfo),
proc_info_argmodes(CallProcInfo, CallArgModes),
- ArgVars = list__map(foreign_arg_var, Args),
+ ArgVars = list.map(foreign_arg_var, Args),
partition_call_args(Module, CallArgModes, ArgVars, _InVars, OutVars),
goal_info_get_context(GoalInfo, Context),
( is_termination_known(Module, proc(CallPredId, CallProcId)) ->
- error_if_intersect(OutVars, Context, pragma_foreign_code,
- !Info)
+ error_if_intersect(OutVars, Context, pragma_foreign_code, !Info)
;
( attributes_imply_termination(Attributes) ->
- error_if_intersect(OutVars, Context,
- pragma_foreign_code, !Info)
+ error_if_intersect(OutVars, Context, pragma_foreign_code, !Info)
;
- add_error(Context, does_not_term_pragma(CallPredId),
- Params, !Info)
+ add_error(Context, does_not_term_pragma(CallPredId), Params, !Info)
)
).
@@ -233,11 +237,10 @@
Details = higher_order(Var, _, _, _),
ClosureValueMap = goal_info_get_ho_values(GoalInfo),
%
- % If closure analysis has identified a set of values
- % this higher-order variable can take, then we can check
- % if they terminate. We cannot anything about the
- % size of the arguments of the higher-order call, so
- % we assume that they are unbounded.
+ % If closure analysis has identified a set of values this higher-order
+ % variable can take, then we can check if they terminate. We cannot
+ % anything about the size of the arguments of the higher-order call,
+ % so we assume that they are unbounded.
%
params_get_module_info(Params, Module),
( ClosureValues0 = ClosureValueMap ^ elem(Var) ->
@@ -246,13 +249,10 @@
Terminating, NonTerminating),
(
NonTerminating = [],
- partition_call_args(Module, ArgModes, Args,
- _InVars, OutVars),
+ partition_call_args(Module, ArgModes, Args, _InVars, OutVars),
params_get_ppid(Params, PPId),
- Error = ho_inf_termination_const(PPId,
- Terminating),
- error_if_intersect(OutVars, Context, Error,
- !Info)
+ Error = ho_inf_termination_const(PPId, Terminating),
+ error_if_intersect(OutVars, Context, Error, !Info)
;
NonTerminating = [_|_],
% XXX We should tell the user what the
@@ -315,9 +315,9 @@
CallArgSizeInfo = no,
% We should get to this point only in pass 1.
% In pass 2, OutputSuppliersMap will be empty,
- % which will lead to a runtime abort in map__lookup.
+ % which will lead to a runtime abort in map.lookup.
params_get_output_suppliers(Params, OutputSuppliersMap),
- map__lookup(OutputSuppliersMap, CallPPId, OutputSuppliers),
+ map.lookup(OutputSuppliersMap, CallPPId, OutputSuppliers),
remove_unused_args(InVars, Args, OutputSuppliers, UsedInVars),
record_change(UsedInVars, OutVars, 0, [CallPPId], !Info)
),
@@ -347,12 +347,12 @@
% Do we start another path?
(
params_get_rec_input_suppliers(Params, RecInputSuppliersMap),
- map__search(RecInputSuppliersMap, CallPPId, RecInputSuppliers)
+ map.search(RecInputSuppliersMap, CallPPId, RecInputSuppliers)
->
% We should get to this point only in pass 2, and then
% only if this call is to a procedure in the current SCC.
% In pass 1, RecInputSuppliersMap will be empty.
-
+ %
compute_rec_start_vars(Args, RecInputSuppliers, Bag),
PathStart = yes(CallPPId - Context),
NewPath = path_info(PPId, PathStart, 0, [], Bag),
@@ -362,14 +362,14 @@
).
traverse_goal_2(shorthand(_), _, _, _, _) :-
- % these should have been expanded out by now
+ % These should have been expanded out by now.
unexpected(this_file, "traverse_goal_2/5: shorthand goal.").
%-----------------------------------------------------------------------------%
% Traverse_conj should be invoked with a reversed list of goals.
% This is to keep stack consumption down.
-
+ %
:- pred traverse_conj(list(hlds_goal)::in, traversal_params::in,
traversal_info::in, traversal_info::out) is det.
@@ -382,7 +382,7 @@
traversal_info::in, traversal_info::out) is det.
traverse_disj([], _, _, ok(Empty, [])) :-
- set__init(Empty).
+ set.init(Empty).
traverse_disj([Goal | Goals], Params, !Info) :-
traverse_goal(Goal, Params, !.Info, GoalInfo),
traverse_disj(Goals, Params, !.Info, GoalsInfo),
@@ -392,7 +392,7 @@
traversal_info::in, traversal_info::out) is det.
traverse_switch([], _, _, ok(Empty, [])) :-
- set__init(Empty).
+ set.init(Empty).
traverse_switch([case(_, Goal) | Cases], Params, !Info) :-
traverse_goal(Goal, Params, !.Info, GoalInfo),
traverse_switch(Cases, Params, !.Info, CasesInfo),
@@ -404,13 +404,13 @@
cannot_succeed(error(Errors, CanLoop), error(Errors, CanLoop)).
cannot_succeed(ok(_, CanLoop), ok(Empty, CanLoop)) :-
- set__init(Empty).
+ set.init(Empty).
:- pred add_path(path_info::in, traversal_info::in, traversal_info::out) is det.
add_path(_, error(Errors, CanLoop), error(Errors, CanLoop)).
add_path(Path, ok(Paths0, CanLoop), ok(Paths, CanLoop)) :-
- set__insert(Paths0, Path, Paths).
+ set.insert(Paths0, Path, Paths).
:- pred add_error(prog_context::in, termination_error::in,
traversal_params::in, traversal_info::in, traversal_info::out) is det.
@@ -419,7 +419,7 @@
error(Errors, CanLoop)) :-
Errors1 = [Context - Error | Errors0],
params_get_max_errors(Params, MaxErrors),
- list__take_upto(MaxErrors, Errors1, Errors).
+ list.take_upto(MaxErrors, Errors1, Errors).
add_error(Context, Error, _, ok(_, CanLoop),
error([Context - Error], CanLoop)).
@@ -430,12 +430,12 @@
error(Errors, CanLoop)) :-
CanLoop1 = [Context - Error | CanLoop0],
params_get_max_errors(Params, MaxErrors),
- list__take_upto(MaxErrors, CanLoop1, CanLoop).
+ list.take_upto(MaxErrors, CanLoop1, CanLoop).
called_can_loop(Context, Error, Params, ok(Paths, CanLoop0),
ok(Paths, CanLoop)) :-
CanLoop1 = [Context - Error | CanLoop0],
params_get_max_errors(Params, MaxErrors),
- list__take_upto(MaxErrors, CanLoop1, CanLoop).
+ list.take_upto(MaxErrors, CanLoop1, CanLoop).
:- pred combine_paths(traversal_info::in, traversal_info::in,
traversal_params::in, traversal_info::out) is det.
@@ -443,31 +443,31 @@
combine_paths(error(Errors1, CanLoop1), error(Errors2, CanLoop2), Params,
error(Errors, CanLoop)) :-
params_get_max_errors(Params, MaxErrors),
- list__append(Errors1, Errors2, Errors3),
- list__take_upto(MaxErrors, Errors3, Errors),
- list__append(CanLoop1, CanLoop2, CanLoop3),
- list__take_upto(MaxErrors, CanLoop3, CanLoop).
+ list.append(Errors1, Errors2, Errors3),
+ list.take_upto(MaxErrors, Errors3, Errors),
+ list.append(CanLoop1, CanLoop2, CanLoop3),
+ list.take_upto(MaxErrors, CanLoop3, CanLoop).
combine_paths(error(Errors1, CanLoop1), ok(_, CanLoop2), Params,
error(Errors1, CanLoop)) :-
params_get_max_errors(Params, MaxErrors),
- list__append(CanLoop1, CanLoop2, CanLoop3),
- list__take_upto(MaxErrors, CanLoop3, CanLoop).
+ list.append(CanLoop1, CanLoop2, CanLoop3),
+ list.take_upto(MaxErrors, CanLoop3, CanLoop).
combine_paths(ok(_, CanLoop1), error(Errors2, CanLoop2), Params,
error(Errors2, CanLoop)) :-
params_get_max_errors(Params, MaxErrors),
- list__append(CanLoop1, CanLoop2, CanLoop3),
- list__take_upto(MaxErrors, CanLoop3, CanLoop).
+ list.append(CanLoop1, CanLoop2, CanLoop3),
+ list.take_upto(MaxErrors, CanLoop3, CanLoop).
combine_paths(ok(Paths1, CanLoop1), ok(Paths2, CanLoop2), Params,
Info) :-
params_get_max_errors(Params, MaxErrors),
- list__append(CanLoop1, CanLoop2, CanLoop3),
- list__take_upto(MaxErrors, CanLoop3, CanLoop),
- set__union(Paths2, Paths1, Paths),
+ list.append(CanLoop1, CanLoop2, CanLoop3),
+ list.take_upto(MaxErrors, CanLoop3, CanLoop),
+ set.union(Paths2, Paths1, Paths),
params_get_max_paths(Params, MaxPaths),
(
% Don't try to track the state of too many paths;
% doing so can require too much memory.
- set__count(Paths, Count),
+ set.count(Paths, Count),
Count =< MaxPaths
->
Info = ok(Paths, CanLoop)
@@ -482,7 +482,7 @@
bag(prog_var)::out) is det.
compute_rec_start_vars([], [], Out) :-
- bag__init(Out).
+ bag.init(Out).
compute_rec_start_vars([_|_], [], _Out) :-
unexpected(this_file,
"compute_rec_start_vars/3: unmatched variables.").
@@ -493,7 +493,7 @@
Out) :-
compute_rec_start_vars(Vars, RecInputSuppliers, Out1),
( RecInputSupplier = yes ->
- bag__insert(Out1, Var, Out)
+ bag.insert(Out1, Var, Out)
;
Out = Out1
).
@@ -508,7 +508,7 @@
% sign of the norm of f and after the membership of X in either the
% input or output bags. The predicate fails if invoked on a higher
% order unification.
-
+ %
:- pred unify_change(prog_var::in, cons_id::in, list(prog_var)::in,
list(uni_mode)::in, traversal_params::in, int::out, bag(prog_var)::out,
bag(prog_var)::out) is semidet.
@@ -516,7 +516,7 @@
unify_change(OutVar, ConsId, Args0, Modes0, Params, Gamma, InVars, OutVars) :-
params_get_functor_info(Params, FunctorInfo),
params_get_var_types(Params, VarTypes),
- map__lookup(VarTypes, OutVar, Type),
+ map.lookup(VarTypes, OutVar, Type),
\+ type_is_higher_order(Type, _, _, _, _),
( type_to_ctor_and_args(Type, TypeCtor, _) ->
params_get_module_info(Params, Module),
@@ -532,13 +532,13 @@
list(prog_var)::out, list(uni_mode)::in, list(uni_mode)::out) is det.
filter_args_and_modes(VarTypes, Args0, Args, Modes0, Modes) :-
- assoc_list__from_corresponding_lists(Args0, Modes0, ArgsAndModes0),
+ assoc_list.from_corresponding_lists(Args0, Modes0, ArgsAndModes0),
IsNotTypeInfo = (pred(ArgMode::in) is semidet :-
- map__lookup(VarTypes, fst(ArgMode), Type),
+ map.lookup(VarTypes, fst(ArgMode), Type),
not is_introduced_type_info_type(Type)
),
- list__filter(IsNotTypeInfo, ArgsAndModes0, ArgsAndModes),
- assoc_list__keys_and_values(ArgsAndModes, Args, Modes).
+ list.filter(IsNotTypeInfo, ArgsAndModes0, ArgsAndModes),
+ assoc_list.keys_and_values(ArgsAndModes, Args, Modes).
%-----------------------------------------------------------------------------%
@@ -548,8 +548,8 @@
record_change(_, _, _, _, error(Errors, CanLoop), error(Errors, CanLoop)).
record_change(InVars, OutVars, Gamma, CalledPPIds, ok(Paths0, CanLoop),
ok(NewPaths, CanLoop)) :-
- set__to_sorted_list(Paths0, PathsList0),
- set__init(NewPaths0),
+ set.to_sorted_list(Paths0, PathsList0),
+ set.init(NewPaths0),
record_change_2(PathsList0, InVars, OutVars, Gamma, CalledPPIds,
NewPaths0, NewPaths).
@@ -561,18 +561,18 @@
record_change_2([Path0 | Paths0], InVars, OutVars, CallGamma, CallPPIds,
!PathSet) :-
Path0 = path_info(ProcData, Start, Gamma0, PPIds0, Vars0),
- ( bag__intersect(OutVars, Vars0) ->
+ ( bag.intersect(OutVars, Vars0) ->
% The change produces some active variables.
Gamma = CallGamma + Gamma0,
- list__append(CallPPIds, PPIds0, PPIds),
- bag__subtract(Vars0, OutVars, Vars1),
- bag__union(InVars, Vars1, Vars),
+ list.append(CallPPIds, PPIds0, PPIds),
+ bag.subtract(Vars0, OutVars, Vars1),
+ bag.union(InVars, Vars1, Vars),
Path = path_info(ProcData, Start, Gamma, PPIds, Vars)
;
% The change produces no active variables.
Path = Path0
),
- set__insert(!.PathSet, Path, !:PathSet),
+ svset.insert(Path, !PathSet),
record_change_2(Paths0, InVars, OutVars, CallGamma, CallPPIds,
!PathSet).
@@ -584,7 +584,7 @@
error_if_intersect(_, _, _, error(Errors, CanLoop), error(Errors, CanLoop)).
error_if_intersect(OutVars, Context, ErrorMsg, ok(Paths, CanLoop), Info) :-
(
- set__to_sorted_list(Paths, PathList),
+ set.to_sorted_list(Paths, PathList),
some_active_vars_in_bag(PathList, OutVars)
->
Info = error([Context - ErrorMsg], CanLoop)
@@ -598,7 +598,7 @@
some_active_vars_in_bag([Path | Paths], OutVars) :-
(
Path = path_info(_, _, _, _, Vars),
- bag__intersect(Vars, OutVars)
+ bag.intersect(Vars, OutVars)
;
some_active_vars_in_bag(Paths, OutVars)
).
@@ -606,28 +606,36 @@
%-----------------------------------------------------------------------------%
upper_bound_active_vars([], ActiveVars) :-
- bag__init(ActiveVars).
+ bag.init(ActiveVars).
upper_bound_active_vars([Path | Paths], ActiveVars) :-
upper_bound_active_vars(Paths, ActiveVars1),
Path = path_info(_, _, _, _, ActiveVars2),
- bag__least_upper_bound(ActiveVars1, ActiveVars2, ActiveVars).
+ bag.least_upper_bound(ActiveVars1, ActiveVars2, ActiveVars).
%-----------------------------------------------------------------------------%
:- type traversal_params
---> traversal_params(
module_info,
+
functor_info,
+
pred_proc_id, % The procedure we are tracing through.
+
prog_context, % The context of the procedure.
- map(prog_var, type),
+
+ vartypes,
+
map(pred_proc_id, list(bool)),
% Output suppliers of each procedure.
% Empty during pass 2.
+
map(pred_proc_id, list(bool)),
% Rec input suppliers of each procedure.
% Empty during pass 1.
+
int, % Max number of errors to gather.
+
int % Max number of paths to analyze.
).
@@ -646,7 +654,7 @@
is det.
:- pred params_get_context(traversal_params::in, prog_context::out)
is det.
-:- pred params_get_var_types(traversal_params::in, map(prog_var, type)::out)
+:- pred params_get_var_types(traversal_params::in, vartypes::out)
is det.
:- pred params_get_output_suppliers(traversal_params::in,
map(pred_proc_id, list(bool))::out) is det.
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list