[m-rev.] for review: rtti_varmaps

[Julien Fischer]

On Sun, 17 Jul 2005, Mark Brown wrote:

> Estimated hours taken: 25
> Branches: main
>
> Package the type_info_varmap and typeclass_info_varmap types into an ADT
> called rtti_varmaps.  There are two main purposes for this:
>
> 	- We wish to extend this set of maps with new maps.  Doing this
> 	will be a lot easier and less error prone if all of the maps are
> 	packaged in a single data structure.
>
> 	- Any new maps that we add may contain redundant information that
> 	just makes searching the maps more efficient.  Therefore they must
> 	be kept consistent with the existing maps.  Having all the maps
> 	inside an ADT makes it easier to ensure this.
>
> This change also includes two extensions to the maps.  First, the
> typeclass_info_map is made reversible so that it is possible to efficiently
> look up the constraint for a given typeclass_info variable.  Second, a new
> map from prog_vars to types makes it possible to efficiently look up the
> type that a given type_info variable is for.  These two changes mean that
> it is no longer necessary to consult the argument of type_info/1 or
> typeclass_info/1 to find this information.  (We still do put that information
> there, though; changing the RTTI is left for a separate change.)
>
> compiler/hlds_pred.m:
> 	Move items relating to type_infos and typeclass_infos into a section
> 	of their own.
>
> 	Add a type `rtti_var_info' to hold information about the contents
> 	of a type_info or typeclass_info variable.
>
> 	Define the rtti_varmaps abstract data type.  This data structure
> 	consists of the type_info_varmap and the typeclass_info_varmap.
> 	A new map, type_info_type_map, is added,  which is like the inverse

That's a little awkward.  How about:

	Add a new map, type_info_var_map, that is ...

> 	to the type_info_varmap.  The difference is that the latter can
> 	point to locations that are inside a typeclass_info variable,
> 	whereas the former only refers to type_info variables.  Note that
> 	the combined maps do not form a bijection, or even an injection,
> 	since it is possible for two different type variables to point to
> 	the same location (that is, if they are aliased).
>
> 	Make the typeclass_info_varmap reversible, by using the new module
> 	injection.m.  Unlike the type_info_varmap, this map is always
> 	injective since the same typeclass_info cannot be used for two
> 	different constraints.
>
> 	The predicates rtti_det_insert_type_info_locn and set_type_info_locn,
> 	which update the type_info_varmap, contain sanity checks to ensure
> 	that only type variables that have already been registered with
> 	the type_info_type_map are used, and that the information in both
> 	maps are consistent.
>
s/are/is/

> 	Use the rtti_varmaps structure in proc_info and clauses_info, in
> 	place of type_info_varmap and typeclass_info_varmap.
>
> compiler/polymorphism.m:
> 	Remove polymorphism__type_info_or_ctor_type/2 and
> 	polymorphism__typeclass_info_class_constraint/2, to ensure that
> 	nobody tries to use the information in the type argument.  Replace
> 	them with two similar predicates that test if a type is type_info
> 	or typeclass_info, but that don't return the argument.
>
> 	Ensure that the new type_info_type_map in the rtti_varmaps is kept
> 	up to date by threading the rtti_varmaps through a few more places.
> 	Some of these places are exported, so this part of the change
> 	affects other modules as well.
>
> 	Fix a comment that referred to a non-existent predicate.
>
> compiler/type_util.m:
> 	Remove the predicates apply_substitutions_to_var_map/5 and
> 	apply_substitutions_to_typeclass_var_map/5.  The functionality
> 	is now provided by the new ADT.
>
> compiler/cse_detection.m:
> 	Rewrite update_existential_data_structures/4 to use the interface
> 	provided by rtti_varmaps.  The algorithm for doing this has changed
> 	in the following ways:
>
> 		- The first pass, which builds a map from changed locations
> 		in the first branch to the tvars concerned, is modified
> 		slightly to traverse over the keys instead of over key-value
> 		pairs.
>
> 		- The second pass, which previously calculated the induced
> 		type substitution and reconstructed the type_info_varmap
> 		now only does the former.
>
> 		- Applying the prog_var transformation and the induced type
> 		substitution is done at the end, using the interface to
> 		rtti_varmaps.
>
> compiler/goal_util.m:
> 	Rewrite goal_util__extra_nonlocal_typeinfos/6 to avoid the need
> 	for using map__member/3 on the typeclass_info_varmap (about which
> 	the existing comments say "this is probably not very efficient..."),
> 	and to be more efficient in general.
>
> 	Previously, we nondeterministically generated non-local type vars
> 	and then tested each constraint to see if it had the type var in it.
> 	Now, we go through each constraint one at a time and check if any of
> 	the type variables in it are non-local.  This is more efficient
> 	because we only need to find one non-local type in order to include
> 	the typeclass_info in the non-locals -- the remaining (duplicate)
> 	solutions are pruned away.
>
> compiler/higher_order.m:
> 	Use the new maps instead of looking at the arguments of type_info/1
> 	and typeclass_info/1 types.  We plan to remove this information
> 	from type_info and typeclass_info types in future.
>
> 	Previously, this module used the type argument in order to update
> 	the varmaps when the curried arguments of a higher order call are
> 	added as arguments to the procedure in which the call occurs.
> 	We now look up this information at the point where the curried arg
> 	variables are known, and store this information in higher_order_arg
> 	alongside the types where it used to be stored.  This structure is
> 	threaded through to the place where the information is needed.
>
> 	Fix a cut and paste bug in higher_order_arg_depth/1.  It was
> 	previously calling higher_order_args_size/1 in the recursive
> 	call, instead of calling higher_order_args_depth/1.
>
I wonder if that's what's causing some of the test cases to currently
fail ...

> compiler/inlining.m:
> 	In inlining__do_inline_call, apply the substitutions to the entire
> 	rtti_varmaps structure, not just to the type_info_varmap.  (XXX Is
> 	there a good reason why the substitution should _not_ be applied
> 	to the typeclass_info varmap?)
>
> compiler/magic_util.m:
> 	Avoid using polymorphism__type_info_or_ctor_type/2 and
> 	polymorphism__typeclass_info_class_constraint/2, as these are
> 	no longer supported.
>
> compiler/*.m:
> 	Straightforward changes to use the new ADT.
>
> library/injection.m:
> 	New library module.  This provides an `injection' type which is
> 	similar to the existing `bimap' type in that it implements
> 	back-to-back maps, but doesn't have such stringent invariants
> 	imposed.  In particular, the reverse map is not required to be
> 	innjective.
s/innjective/injective/

I wonder if we should eventually rename the `bimap' type `bijection'
then?

> 	This type is used to model the relationship between prog_constraints
> 	and program variables that hold typeclass_infos for them.  Namely,
> 	the typeclass_info for a constraint can be held in two different
> 	variables, but one variable can never hold the typeclass_info for
> 	two distinct constraints.
>
> library/library.m:
> 	Add the new library module.
>
> library/list.m:
> 	Add list__foldl_corresponding and list__foldl2_corresponding, which
> 	traverse two lists in parallel, which one or two accumulators, and
> 	abort if there is a length mismatch.
>
> NEWS:
> 	Mention the changes to the standard library.
>
...

> +		% of this map are the new locations, and the values are
> +		% the tvars (from the first branch) that have had their
> +		% locations moved.
> +		%
> +	rtti_varmaps_tvars(RttiVarMaps0, TvarsList),
> +	list__foldl(find_type_info_locn_tvar_map(RttiVarMaps0, FirstOldNewMap),
> +		TvarsList, map__init, NewTvarMap),
> +
> +		% Traverse TVarsList again, this time looking for locations
> +		% in later branches that merge with locations in the first
> +		% branch.  When we find one, add a type substitution which
> +		% represents the type variables that thus got merged.
s/thus got/were/

> +		%
> +	list__foldl(find_merged_tvars(RttiVarMaps0, LaterOldNewMap, NewTvarMap),
> +		TvarsList, map__init, TSubst),
> +
> +		% Apply the full old->new map and the type substitution
> +		% to the rtti_varmaps, and apply the type substitution to the
> +		% vartypes.
> +		%
> +	list__append(FirstOldNew, LaterOldNew, OldNew),
> +	map__from_assoc_list(OldNew, OldNewMap),
> +	apply_substitutions_to_rtti_varmaps(TSubst, map__init, OldNewMap,
> +		RttiVarMaps0, RttiVarMaps),
> +	map__map_values(apply_tvar_rename(TSubst), VarTypes0, VarTypes),
>
> -	!:CseInfo = !.CseInfo ^ type_info_varmap := TypeInfoVarMap,
> -	!:CseInfo = !.CseInfo ^ typeclass_info_varmap := TypeClassInfoVarMap,
> +	!:CseInfo = !.CseInfo ^ rtti_varmaps := RttiVarMaps,
>  	!:CseInfo = !.CseInfo ^ vartypes := VarTypes.

...

> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/hlds_pred.m,v
> retrieving revision 1.165
> diff -u -r1.165 hlds_pred.m
> --- compiler/hlds_pred.m	8 Jul 2005 04:22:02 -0000	1.165
> +++ compiler/hlds_pred.m	13 Jul 2005 10:47:29 -0000
> @@ -39,6 +39,7 @@
>  :- implementation.
>
>  % Parse tree modules.
> +:- import_module parse_tree__prog_type.
>  :- import_module parse_tree__prog_util.
>
>  % HLDS modules.
> @@ -53,9 +54,11 @@
>  :- import_module libs__options.
>
>  % Standard library modules.
> +:- import_module injection.
>  :- import_module int.
>  :- import_module require.
>  :- import_module string.
> +:- import_module svmap.
>  :- import_module term.
>  :- import_module varset.
>
> @@ -189,6 +192,471 @@
>
>  %-----------------------------------------------------------------------------%
>
> +	% Types and predicates to store information about RTTI.
> +

If this is a section heading, it should be formatted as the coding
standard suggests. e.g.

	%-------------------------------------...
	%
	% Types and predicates to store information about RTTI
	%


> +	% Describes the class constraints on an instance method implementation.
> +	% This information is used by polymorphism.m to ensure that the
> +	% type_info and typeclass_info arguments are added in the order in
> +	% which they will be passed in by do_call_class_method.
> +	%
> +:- type instance_method_constraints
> +	---> instance_method_constraints(
> +		class_id,
> +		list(type),		% The types in the head of the
> +					% instance declaration.
> +		list(prog_constraint),	% The universal constraints
> +					% on the instance declaration.
> +		prog_constraints	% The contraints on the method's
> +					% type declaration in the
> +					% `:- typeclass' declaration.
> +	).
> +
> +	%  A type_info_locn specifies how to access a type_info.
> +	%
> +:- type type_info_locn
> +	--->	type_info(prog_var)
> +				% It is a normal type_info, i.e. the type
> +				% is not constrained.
> +
> +	;	typeclass_info(prog_var, int).
> +				% The type_info is packed inside a
> +				% typeclass_info. If the int is N, it is
> +				% the Nth type_info inside the typeclass_info,
> +				% but there may be several superclass pointers
> +				% before the block of type_infos, so it won't
> +				% be the Nth word of the typeclass_info.
> +				%
> +				% To find the type_info inside the
> +				% typeclass_info, use the predicate
> +				% type_info_from_typeclass_info from Mercury
> +				% code; from C code use the macro
> +				% MR_typeclass_info_superclass_info.
> +
> +	% type_info_locn_var(TypeInfoLocn, Var):
> +	%
> +	% Var is the variable corresponding to the TypeInfoLocn. Note
> +	% that this does *not* mean that Var is a type_info; it may be
> +	% a typeclass_info in which the type_info is nested.
> +	%
> +:- pred type_info_locn_var(type_info_locn::in, prog_var::out) is det.
> +
> +:- pred type_info_locn_set_var(prog_var::in,
> +	type_info_locn::in, type_info_locn::out) is det.
> +
> +	% This type describes the contents of a prog_var.
> +	%
> +:- type rtti_var_info
> +	--->	type_info_var(type)
> +			% The variable holds a type_info for the given type.
> +
> +	;	typeclass_info_var(prog_constraint)
> +			% The variable holds a typeclass_info for the given
> +			% constraint.
> +
> +	;	non_rtti_var.
> +			% The variable does not directly hold any run time
> +			% type information.
> +
> +	% This records information about how type_infos and typeclass_infos
> +	% were introduced in the polymorphism transformation.
> +	%
> +:- type rtti_varmaps.
> +
> +	% Returns an empty rtti_varmaps structure.
> +	%
> +:- pred rtti_varmaps_init(rtti_varmaps::out) is det.
> +
> +	% Succeeds iff the rtti_varmaps contain no information about any
> +	% type variables.
> +	%
> +:- pred rtti_varmaps_no_tvars(rtti_varmaps::in) is semidet.
> +
> +	% Find the location of a type_info.
> +	%
> +:- pred rtti_lookup_type_info_locn(rtti_varmaps::in, tvar::in,
> +	type_info_locn::out) is det.
> +
> +	% Find the location of a type_info, if it is known.
> +	%
> +:- pred rtti_search_type_info_locn(rtti_varmaps::in, tvar::in,
> +	type_info_locn::out) is semidet.
> +
> +	% Find the prog_var which contains the typeclass_info for a given
> +	% constraint.
> +	%
> +:- pred rtti_lookup_typeclass_info_var(rtti_varmaps::in, prog_constraint::in,
> +	prog_var::out) is det.
> +
> +	% Find the prog_var which contains the typeclass_info for a given
> +	% constraint, if it is known.
> +	%
> +:- pred rtti_search_typeclass_info_var(rtti_varmaps::in, prog_constraint::in,
> +	prog_var::out) is semidet.
> +
> +	% Find what RTTI, if any, is stored in a prog_var.
> +	%
> +:- pred rtti_varmaps_var_info(rtti_varmaps::in, prog_var::in,
> +	rtti_var_info::out) is det.
> +
> +	% Insert the location of a type_info.  Abort if such information
> +	% already exists.
> +	%
> +:- pred rtti_det_insert_type_info_locn(tvar::in, type_info_locn::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% Set the location of a type_info, overwriting any previous
> +	% information.
> +	%
> +:- pred rtti_set_type_info_locn(tvar::in, type_info_locn::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% Insert the prog_var which contains the typeclass_info for a
> +	% given constraint.  Abort if such information already exists.
> +	%
> +:- pred rtti_det_insert_typeclass_info_var(prog_constraint::in, prog_var::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% Set the prog_var which contains the typeclass_info for a given
> +	% constraint, overwriting any previous information.
> +	%
> +:- pred rtti_set_typeclass_info_var(prog_constraint::in, prog_var::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% For a prog_var which holds a type_info, set the type that the
> +	% type_info is for.  Abort if such information already exists.
> +	%
> +:- pred rtti_det_insert_type_info_type(prog_var::in, (type)::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% Returns all of the tvars that we have information about in the
> +	% rtti_varmaps structure.
> +	%
> +:- pred rtti_varmaps_tvars(rtti_varmaps::in, list(tvar)::out) is det.
> +
> +	% Returns all of the prog_constraints that we have information
> +	% about in the rtti_varmaps structure.
> +	%
> +:- pred rtti_varmaps_constraints(rtti_varmaps::in, list(prog_constraint)::out)
> +	is det.
> +
> +	% apply_substitutions_to_rtti_varmaps(TRenaming, TSubst, Subst,
> +	% 	!RttiVarMaps)
> +	%
> +	% Apply substitutions to the rtti_varmaps data.  TRenaming is applied
> +	% to all types first, then TSubst is applied to all types.  Subst
> +	% is applied to all prog_vars.
> +	%
> +:- pred apply_substitutions_to_rtti_varmaps(tsubst::in, tsubst::in,
> +	map(prog_var, prog_var)::in, rtti_varmaps::in, rtti_varmaps::out)
> +	is det.
> +
> +	% rtti_varmaps_transform_constraints(Pred, !RttiVarMaps)
> +	%
> +	% Apply the transformation predicate to every constraint appearing
> +	% in the rtti_varmaps structure.
> +	%
> +:- pred rtti_varmaps_transform_constraints(
> +	pred(prog_constraint, prog_constraint)::in(pred(in, out) is det),
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +	% rtti_varmaps_overlay(A, B, C)
> +	%
> +	% Merge the information in rtti_varmaps A and B to produce C.  Where
> +	% information conflicts, use the information in B rather than A.
> +	%
> +:- pred rtti_varmaps_overlay(rtti_varmaps::in, rtti_varmaps::in,
> +	rtti_varmaps::out) is det.
> +
> +%-----------------------------------------------------------------------------%
> +
> +:- implementation.
> +
> +type_info_locn_var(type_info(Var), Var).
> +type_info_locn_var(typeclass_info(Var, _), Var).
> +
> +type_info_locn_set_var(Var, type_info(_), type_info(Var)).
> +type_info_locn_set_var(Var, typeclass_info(_, Num), typeclass_info(Var, Num)).
> +
> +:- type rtti_varmaps
> +	---> rtti_varmaps(
> +		tci_varmap		:: typeclass_info_varmap,
> +		ti_varmap		:: type_info_varmap,
> +		ti_type_map		:: type_info_type_map
> +	).
> +
> +	% A typeclass_info_varmap is a map which for each type class constraint
> +	% records which variable contains the typeclass_info for that
> +	% constraint.  The map is reversible in the sense that we can
> +	% efficiently look up which constraint, if any, has its
> +	% typeclass_info stored in a given prog_var.
> +	%
> +:- type typeclass_info_varmap == injection(prog_constraint, prog_var).
> +
> +	% A type_info_varmap is a map which for each type variable
> +	% records where the type_info for that type variable is stored.
> +	%
> +	% XXX this doesn't record the information that we want.  For a
> +	% constraint such as foo(list(T)) we can't properly record the
> +	% location of the type_info for T, since it does not occupy a slot
> +	% in the typeclass_info directly, but is inside the type_info for
> +	% list(T).
> +	%
> +:- type type_info_varmap == map(tvar, type_info_locn).
> +
> +	% Every program variable which holds a type_info is a key in this
> +	% map.  The value associated with a given key is the type that the
> +	% type_info is for.
> +	%
> +:- type type_info_type_map == map(prog_var, type).
> +
> +rtti_varmaps_init(rtti_varmaps(TCIMap, TIMap, TypeMap)) :-
> +	injection__init(TCIMap),
> +	map__init(TIMap),
> +	map__init(TypeMap).
> +
> +rtti_varmaps_no_tvars(VarMaps) :-
> +	map__is_empty(VarMaps ^ ti_varmap).
> +
> +rtti_lookup_type_info_locn(VarMaps, TVar, Locn) :-
> +	map__lookup(VarMaps ^ ti_varmap, TVar, Locn).
> +
> +rtti_search_type_info_locn(VarMaps, TVar, Locn) :-
> +	map__search(VarMaps ^ ti_varmap, TVar, Locn).
> +
> +rtti_lookup_typeclass_info_var(VarMaps, Constraint, ProgVar) :-
> +	injection__lookup(VarMaps ^ tci_varmap, Constraint, ProgVar).
> +
> +rtti_search_typeclass_info_var(VarMaps, Constraint, ProgVar) :-
> +	injection__forward_search(VarMaps ^ tci_varmap, Constraint, ProgVar).
> +
> +rtti_varmaps_var_info(VarMaps, Var, VarInfo) :-
> +	(
> +		map__search(VarMaps ^ ti_type_map, Var, Type)
> +	->
> +		VarInfo = type_info_var(Type)
> +	;
> +		injection__reverse_search(VarMaps ^ tci_varmap, Constraint,
> +			Var)
> +	->
> +		VarInfo = typeclass_info_var(Constraint)
> +	;
> +		VarInfo = non_rtti_var
> +	).
> +
> +rtti_det_insert_type_info_locn(TVar, Locn, !VarMaps) :-
> +	Map0 = !.VarMaps ^ ti_varmap,
> +	map__det_insert(Map0, TVar, Locn, Map),
> +	!:VarMaps = !.VarMaps ^ ti_varmap := Map,
> +	maybe_check_type_info_var(Locn, TVar, !VarMaps).
> +
> +rtti_set_type_info_locn(TVar, Locn, !VarMaps) :-
> +	Map0 = !.VarMaps ^ ti_varmap,
> +	map__set(Map0, TVar, Locn, Map),
> +	!:VarMaps = !.VarMaps ^ ti_varmap := Map,
> +	maybe_check_type_info_var(Locn, TVar, !VarMaps).
> +
> +:- pred maybe_check_type_info_var(type_info_locn::in, tvar::in,
> +	rtti_varmaps::in, rtti_varmaps::out) is det.
> +
> +maybe_check_type_info_var(type_info(Var), TVar, !VarMaps) :-
> +	(
> +		map__search(!.VarMaps ^ ti_type_map, Var, Type)
> +	->
> +		(
> +			Type = term__variable(TVar)
> +		->
> +			true
> +		;
> +			error("maybe_check_type_info_var: inconsistent info")
Code inside the compiler should ideally call
error_util.unexpected/2 rather than error/1.

> +		)
> +	;
> +		error("maybe_check_type_info_var: missing info")
> +	).
> +maybe_check_type_info_var(typeclass_info(_, _), _, !VarMaps).
> +

...

> Index: library/injection.m
> ===================================================================
> RCS file: library/injection.m
> diff -N library/injection.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ library/injection.m	12 Jul 2005 13:26:42 -0000
> @@ -0,0 +1,682 @@
> +%---------------------------------------------------------------------------%
> +% Copyright (C) 2005 The University of Melbourne.
> +% This file may only be copied under the terms of the GNU Library General
> +% Public License - see the file COPYING.LIB in the Mercury distribution.
> +%-----------------------------------------------------------------------------%
> +%
> +% File: injection.m
> +% Author: mark
> +%
> +% This module provides the `injection' ADT.  An injection is like a `map'
> +% (see map.m) but it allows efficient reverse lookups, similarly to `bimap'.
> +% The difference between an injection and a bimap is that there can be
> +% values in the range of the injection that are not returned for any key.
> +%
> +% The invariants on this data structure, which are enforced by this module,
> +% are as follows:
> +%

There is a space-time trade-off involved inmplementing efficient reverse
lookups that I feel ought to mentioned here (it should probably also be mentioned
in bimap's documentation as well).


> +% 1) For any key K, if a forward lookup succeeds with value V then a reverse
> +% lookup of value V will succeed with key K.
> +%
> +% 2) For any value V, if a reverse lookup succeeds with key K then a forward
> +% lookup of key K will succeed with some value (not necessarily V).
> +%
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +
> +:- module injection.
> +:- interface.
> +
> +:- import_module assoc_list.
> +:- import_module list.
> +:- import_module map.
> +
> +%-----------------------------------------------------------------------------%
> +
> +:- type injection(K, V).
> +
> +%-----------------------------------------------------------------------------%
> +
> +	% Initialize an empty injection.
> +	%
> +:- func injection.init = injection(K, V).
> +:- pred injection.init(injection(K, V)::out) is det.
> +
Is the predicate version of injection.init really necessary?

> +	% Check whether an injection is empty.
> +	%
> +:- pred injection.is_empty(injection(K, V)::in) is semidet.
> +
> +	% Search the injection for the value corresponding to a given key.
> +	%
> +:- func injection.forward_search(injection(K, V), K) = V is semidet.
> +:- pred injection.forward_search(injection(K, V)::in, K::in, V::out)
> +	is semidet.
> +
> +	% Search the injection for the key corresponding to a given value.
> +	%
> +:- func injection.reverse_search(injection(K, V), V) = K is semidet.
> +:- pred injection.reverse_search(injection(K, V)::in, K::out, V::in)
> +	is semidet.
> +
> +	% Combined forward/reverse search.  (Declaratively equivalent to
> +	% reverse_search.)
> +	%
> +:- pred injection.search(injection(K, V), K, V).
> +:- mode injection.search(in, in, out) is cc_nondet.
> +:- mode injection.search(in, out, in) is semidet.
> +
> +	% Look up the value for a given key, but throw an exception if it
> +	% is not present.
> +	%
> +:- func injection.lookup(injection(K, V), K) = V.
> +:- pred injection.lookup(injection(K, V)::in, K::in, V::out) is det.
> +
> +	% Look up the key for a given value, but throw an exception if it
> +	% is not present.
> +	%
> +:- func injection.reverse_lookup(injection(K, V), V) = K.
> +:- pred injection.reverse_lookup(injection(K, V)::in, K::out, V::in) is det.
> +
> +	% Return the list of all keys in the injection.
> +	%
> +:- func injection.keys(injection(K, V)) = list(K).
> +:- pred injection.keys(injection(K, V)::in, list(K)::out) is det.
> +
I'd argue for not including the predicate versions of procedures,
like injection.keys, that would naturally be functions; with the
exception of procedures that are candidate for use with
state variable notation.

> +	% Return the list of all values in the injection.
> +	%
> +:- func injection.values(injection(K, V)) = list(V).
> +:- pred injection.values(injection(K, V)::in, list(V)::out) is det.
> +
> +	% Succeeds if the injection contains the given key.
> +	%
> +:- pred injection.contains_key(injection(K, V), K).
> +:- mode injection.contains_key(in, in) is semidet.
> +
Is there any reason you haven't used predmode syntax here (and below)?

> +	% Succeeds if the injection contains the given value.
> +	%
> +:- pred injection.contains_value(injection(K, V), V).
> +:- mode injection.contains_value(in, in) is semidet.
> +
> +	% Insert a new key-value pair into the injection.  Fails if either
> +	% the key or value already exists.
> +	%
> +:- func injection.insert(injection(K, V), K, V) = injection(K, V) is semidet.
> +:- pred injection.insert(injection(K, V)::in, K::in, V::in,
> +	injection(K, V)::out) is semidet.
> +

...

> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +
> +:- implementation.
> +
> +:- import_module require.
> +:- import_module std_util.
> +:- import_module string.
> +:- import_module svmap.
> +
> +:- type injection(K, V)
> +	--->	injection(map(K, V), map(V, K)).
> +
A lot of the code in the implementation of this module would benefit
from using state variable notation, if only to reduce the number of
F0s, R0s etc.

The rest of the diff look okay; assuming that it bootraps in several
different grades (one of which should definitely be a term size
profiling grade), you can commit it.

Julien.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------