[m-rev.] for review by Mark: a note on bug 154
Zoltan Somogyi
zs at csse.unimelb.edu.au
Wed Sep 15 17:01:27 AEST 2010
Mark, I would appreciate your opinion on the comment I added to hlds_rtti.m.
Zoltan.
compiler/hlds_rtti.m:
Note a problem with our current data structure design.
compiler/hlds_rtti.m:
compiler/quantification.m:
Fix some issues of programming style.
cvs diff: Diffing .
Index: hlds_rtti.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_rtti.m,v
retrieving revision 1.20
diff -u -b -r1.20 hlds_rtti.m
--- hlds_rtti.m 30 Oct 2009 03:33:14 -0000 1.20
+++ hlds_rtti.m 15 Sep 2010 06:22:13 -0000
@@ -135,9 +135,9 @@
% 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.
+ % 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.
@@ -212,8 +212,7 @@
:- 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.
+ % 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.
@@ -230,20 +229,20 @@
:- pred rtti_set_typeclass_info_var(prog_constraint::in, prog_var::in,
rtti_varmaps::in, rtti_varmaps::out) is det.
- % Make the given typeclass_info var available for reuse in later
- % goals. Abort if we know nothing about this variable.
+ % Make the given typeclass_info var available for reuse in later goals.
+ % Abort if we know nothing about this variable.
%
:- pred rtti_reuse_typeclass_info_var(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.
+ % 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, mer_type::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, overwriting any previous information.
+ % For a prog_var which holds a type_info, set the type that the type_info
+ % is for, overwriting any previous information.
%
:- pred rtti_set_type_info_type(prog_var::in, mer_type::in,
rtti_varmaps::in, rtti_varmaps::out) is det.
@@ -287,16 +286,16 @@
is det.
% apply_substitutions_to_rtti_varmaps(TRenaming, TSubst, Subst,
- % !RttiVarMaps)
+ % !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.
+ % Apply substitutions to the rtti_varmaps data. First apply TRenaming
+ % to all types, then apply TSubst to all types. Apply Subst to all
+ % prog_vars.
%
:- pred apply_substitutions_to_rtti_varmaps(tvar_renaming::in, tsubst::in,
prog_var_renaming::in, rtti_varmaps::in, rtti_varmaps::out) is det.
- % rtti_varmaps_transform_types(Pred, !RttiVarMaps)
+ % rtti_varmaps_transform_types(Pred, !RttiVarMaps):
%
% Apply the transformation predicate to every type appearing in the
% rtti_varmaps structure, including those in the arguments of constraints.
@@ -305,10 +304,10 @@
pred(mer_type, mer_type)::in(pred(in, out) is det),
rtti_varmaps::in, rtti_varmaps::out) is det.
- % rtti_varmaps_overlay(A, B, C)
+ % 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.
+ % 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.
@@ -423,6 +422,42 @@
% 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).
%
+ % XXX Even the information that is recorded has the wrong key. Consider
+ % a conjunction between:
+ %
+ % - a call that returns an existentially typed result, and
+ % - a goal that uses that existentially typed variable.
+ %
+ % Let us say that the conjunction looks like
+ %
+ % gen_result(X_1, TypeInfo_for_T_2), use_result(TypeInfo_for_T_2, X_1).
+ %
+ % This conjunction can be duplicated, e.g. by switch detection (it could be
+ % in a switch arm that is guarded by a disjunction that handles different
+ % values of the switched-on variable differently) or by tabling.
+ % (This is what happens in Mantis bug #154.)
+ %
+ % In such cases, the renamed-apart duplicated goal would be something like
+ %
+ % gen_result(X_3, TypeInfo_for_T_4), use_result(TypeInfo_for_T_4, X_3).
+ %
+ % Yet the rtti_var_map for the procedure would say that X_3 is of the same
+ % type as X_1, which means that the compiler would think that X_1 and X_3
+ % use the same type_info variable to represent their types. This would be
+ % TypeInfo_for_T_2, even though it won't exist on the execution branch
+ % containing the copied version of the goal.
+ %
+ % I (zs) can see two possible fixes.
+ %
+ % - First, we could have type_info_varmap map each tvar to a nonempty set
+ % of type_info_locns, exactly one of which would be available on every
+ % execution path. It would be the responsibility of other parts of the
+ % compiler to pick the right one.
+ %
+ % - Second, instead of mapping prog_vars to types, and the tvars in those
+ % types to the prog_vars holding their type_infos, we could map each
+ % prog_var directly to a {tvar -> typeinfo progvar} map.
+ %
:- type type_info_varmap == map(tvar, type_info_locn).
% Every program variable which holds a type_info is a key in this map.
@@ -452,28 +487,27 @@
!.RttiVarMaps = rtti_varmaps(TCIMap0, TIMap0, TypeMap0, ConstraintMap0),
map.to_assoc_list(TIMap0, TIList0),
- filter_type_info_varmap(TIList0, [], RevTIList, VarUses),
+ filter_type_info_varmap(TIList0, VarUses, [], RevTIList),
map.from_rev_sorted_assoc_list(RevTIList, TIMap),
map.to_assoc_list(TypeMap0, TypeList0),
- filter_type_info_map(TypeList0, [], RevTypeList, VarUses),
+ filter_type_info_map(TypeList0, VarUses, [], RevTypeList),
map.from_rev_sorted_assoc_list(RevTypeList, TypeMap),
map.to_assoc_list(ConstraintMap0, ConstraintList0),
- filter_constraint_map(ConstraintList0, [], RevConstraintList,
- TCIMap0, TCIMap, VarUses),
- list.reverse(RevConstraintList, ConstraintList),
- map.from_sorted_assoc_list(ConstraintList, ConstraintMap),
+ filter_constraint_map(ConstraintList0, VarUses, [], RevConstraintList,
+ TCIMap0, TCIMap),
+ map.from_rev_sorted_assoc_list(RevConstraintList, ConstraintMap),
!:RttiVarMaps = rtti_varmaps(TCIMap, TIMap, TypeMap, ConstraintMap).
:- pred filter_type_info_varmap(assoc_list(tvar, type_info_locn)::in,
+ array(bool)::in,
assoc_list(tvar, type_info_locn)::in,
- assoc_list(tvar, type_info_locn)::out,
- array(bool)::in) is det.
+ assoc_list(tvar, type_info_locn)::out) is det.
-filter_type_info_varmap([], !RevTVarLocns, _VarUses).
-filter_type_info_varmap([TVarLocn | TVarLocns], !RevTVarLocns, VarUses) :-
+filter_type_info_varmap([], _VarUses, !RevTVarLocns).
+filter_type_info_varmap([TVarLocn | TVarLocns], VarUses, !RevTVarLocns) :-
TVarLocn = _TVar - Locn,
( Locn = type_info(Var)
; Locn = typeclass_info(Var, _)
@@ -486,14 +520,15 @@
;
Used = no
),
- filter_type_info_varmap(TVarLocns, !RevTVarLocns, VarUses).
+ filter_type_info_varmap(TVarLocns, VarUses, !RevTVarLocns).
:- pred filter_type_info_map(assoc_list(prog_var, mer_type)::in,
- assoc_list(prog_var, mer_type)::in, assoc_list(prog_var, mer_type)::out,
- array(bool)::in) is det.
+ array(bool)::in,
+ assoc_list(prog_var, mer_type)::in, assoc_list(prog_var, mer_type)::out)
+ is det.
-filter_type_info_map([], !RevVarTypes, _VarUses).
-filter_type_info_map([VarType | VarTypes], !RevVarTypes, VarUses) :-
+filter_type_info_map([], _VarUses, !RevVarTypes).
+filter_type_info_map([VarType | VarTypes], VarUses, !RevVarTypes) :-
VarType = Var - _Type,
VarNum = var_to_int(Var),
array.unsafe_lookup(VarUses, VarNum, Used),
@@ -503,17 +538,17 @@
;
Used = no
),
- filter_type_info_map(VarTypes, !RevVarTypes, VarUses).
+ filter_type_info_map(VarTypes, VarUses, !RevVarTypes).
:- pred filter_constraint_map(assoc_list(prog_var, prog_constraint)::in,
+ array(bool)::in,
assoc_list(prog_var, prog_constraint)::in,
assoc_list(prog_var, prog_constraint)::out,
- typeclass_info_varmap::in, typeclass_info_varmap::out,
- array(bool)::in) is det.
+ typeclass_info_varmap::in, typeclass_info_varmap::out) is det.
-filter_constraint_map([], !RevVarConstraints, !TCIMap, _VarUses).
-filter_constraint_map([VarConstraint | VarConstraints], !RevVarConstraints,
- !TCIMap, VarUses) :-
+filter_constraint_map([], _VarUses, !RevVarConstraints, !TCIMap).
+filter_constraint_map([VarConstraint | VarConstraints], VarUses,
+ !RevVarConstraints, !TCIMap) :-
VarConstraint = Var - Constraint,
VarNum = var_to_int(Var),
array.unsafe_lookup(VarUses, VarNum, Used),
@@ -524,8 +559,8 @@
Used = no,
map.delete(!.TCIMap, Constraint, !:TCIMap)
),
- filter_constraint_map(VarConstraints, !RevVarConstraints,
- !TCIMap, VarUses).
+ filter_constraint_map(VarConstraints, VarUses,
+ !RevVarConstraints, !TCIMap).
rtti_varmaps_no_tvars(RttiVarMaps) :-
map.is_empty(RttiVarMaps ^ rv_ti_varmap).
@@ -818,12 +853,10 @@
VarMapsB = rtti_varmaps(TCImapB, TImapB, TypeMapB, ConstraintMapB),
% Prefer VarMapsB for this information.
- %
map.overlay(TCImapA, TCImapB, TCImap),
map.overlay(TImapA, TImapB, TImap),
% On the other hand, we insist that this information is consistent.
- %
map.old_merge(TypeMapA, TypeMapB, TypeMap),
map.old_merge(ConstraintMapA, ConstraintMapB, ConstraintMap),
@@ -853,9 +886,8 @@
get_typeinfo_vars_2(Vars, VarTypes, TVarMap, TypeInfoVars)
;
TypeVars = [_ | _],
- % XXX It's possible there are some complications with
- % higher order pred types here -- if so, maybe
- % treat them specially.
+ % XXX It is possible there are some complications with higher order
+ % pred types here -- if so, maybe treat them specially.
% The type_info is either stored in a variable, or in a
% typeclass_info. Either get the type_info variable or
Index: quantification.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/quantification.m,v
retrieving revision 1.137
diff -u -b -r1.137 quantification.m
--- quantification.m 6 Nov 2009 02:22:02 -0000 1.137
+++ quantification.m 15 Sep 2010 05:07:49 -0000
@@ -119,13 +119,42 @@
%-----------------------------------------------------------------------------%
+ % `OutsideVars' are the variables that have occurred free outside
+ % this goal, not counting occurrences in parallel goals and not
+ % counting occurrences in lambda goals, or which have been explicitly
+ % existentially quantified over a scope which includes the current
+ % goal in a negated context.
+ %
+ % `QuantVars' are the variables not in `OutsideVars' that have been
+ % explicitly existentially quantified over a scope which includes the
+ % current goal in a positive (non-negated) context.
+ %
+ % `OutsideLambdaVars' are the variables that have occurred free in
+ % a lambda expression outside this goal, not counting occurrences in
+ % parallel goals (and if this goal is itself inside a lambda
+ % expression, not counting occurrences outside that lambda expression).
+ %
+ % For example, consider
+ %
+ % test :- some [X] (p(X) ; not q(X) ; r(X), s(X)).
+ %
+ % When processing `r(X), s(X)':
+ % OutsideVars will be [] and QuantifiedVars will be [X].
+ % When processing `r(X)':
+ % OutsideVars will be [X] and QuantifiedVars will be [],
+ % since now [X] has occured in a goal (`s(X)') outside of `r(X)'.
+ % When processing `not q(X)':
+ % OutsideVars will be [] and QuantifiedVars will be [X].
+ % When processing `q(X)':
+ % OutsideVars will be [X] and QuantifiedVars will be [],
+ % since the quantification can't be pushed inside the negation.
+ %
% The `outside vars', `lambda outside vars', and `quant vars'
% fields are inputs; the `nonlocals' field is output; and
% the `seen so far', the varset, the types, rtti_varmaps, and the
% warnings fields are threaded (i.e. both input and output).
% We use the convention that the input fields are callee save,
% and the outputs are caller save.
- % The nonlocals_to_recompute field is constant.
%
:- type quant_info
---> quant_info(
@@ -149,40 +178,15 @@
% If you want to debug a new set representation, just import a version
% of the bitset_tester module from tests/hard_coded, and make set_of_var
% equivalent to the bitset_tester type.
-% :- type set_of_var == set(prog_var).
-:- type set_of_var == tree_bitset(prog_var).
-
- % `OutsideVars' are the variables that have occurred free outside
- % this goal, not counting occurrences in parallel goals and not
- % counting occurrences in lambda goals, or which have been explicitly
- % existentially quantified over a scope which includes the current
- % goal in a negated context.
- %
- % `QuantVars' are the variables not in `OutsideVars' that have been
- % explicitly existentially quantified over a scope which includes the
- % current goal in a positive (non-negated) context.
- %
- % `OutsideLambdaVars' are the variables that have occurred free in
- % a lambda expression outside this goal, not counting occurrences in
- % parallel goals (and if this goal is itself inside a lambda
- % expression, not counting occurrences outside that lambda expression).
- %
- % For example, for
- %
- % test :- some [X] (p(X) ; not q(X) ; r(X), s(X)).
- %
- % when processing `r(X), s(X)', OutsideVars will be [] and
- % QuantifiedVars will be [X]; when processing `r(X)',
- % OutsideVars will be [X] and QuantifiedVars will be [],
- % since now [X] has occured in a goal (`s(X)') outside of `r(X)'.
- % When processing `not q(X)', OutsideVars will be [] and
- % QuantifiedVars will be [X]; when processing `q(X)',
- % OutsideVars will be [X] and QuantifiedVars will be [],
- % since the quantification can't be pushed inside the negation.
+:- type set_of_var == set(prog_var).
+% :- type set_of_var == tree_bitset(prog_var).
-:- inst ordinary_nonlocals_maybe_lambda ---> ordinary_nonlocals_maybe_lambda.
-:- inst ordinary_nonlocals_no_lambda ---> ordinary_nonlocals_no_lambda.
-:- inst code_gen_nonlocals_no_lambda ---> code_gen_nonlocals_no_lambda.
+:- inst ordinary_nonlocals_maybe_lambda
+ ---> ordinary_nonlocals_maybe_lambda.
+:- inst ordinary_nonlocals_no_lambda
+ ---> ordinary_nonlocals_no_lambda.
+:- inst code_gen_nonlocals_no_lambda
+ ---> code_gen_nonlocals_no_lambda.
%-----------------------------------------------------------------------------%
@@ -2502,15 +2506,24 @@
get_warnings(Q, Q ^ qi_warnings).
get_rtti_varmaps(Q, Q ^ qi_rtti_varmaps).
-set_outside(Outside, Q, Q ^ qi_outside := Outside).
-set_quant_vars(QuantVars, Q, Q ^ qi_quant_vars := QuantVars).
-set_lambda_outside(LambdaOutside, Q, Q ^ qi_lambda_outside := LambdaOutside).
-set_nonlocals(NonLocals, Q, Q ^ qi_nonlocals := NonLocals).
-set_seen(Seen, Q, Q ^ qi_seen := Seen).
-set_varset(Varset, Q, Q ^ qi_varset := Varset).
-set_vartypes(VarTypes, Q, Q ^ qi_vartypes := VarTypes).
-set_warnings(Warnings, Q, Q ^ qi_warnings := Warnings).
-set_rtti_varmaps(RttiVarMaps, Q, Q ^ qi_rtti_varmaps := RttiVarMaps).
+set_outside(Outside, !Q) :-
+ !Q ^ qi_outside := Outside.
+set_quant_vars(QuantVars, !Q) :-
+ !Q ^ qi_quant_vars := QuantVars.
+set_lambda_outside(LambdaOutside, !Q) :-
+ !Q ^ qi_lambda_outside := LambdaOutside.
+set_nonlocals(NonLocals, !Q) :-
+ !Q ^ qi_nonlocals := NonLocals.
+set_seen(Seen, !Q) :-
+ !Q ^ qi_seen := Seen.
+set_varset(Varset, !Q) :-
+ !Q ^ qi_varset := Varset.
+set_vartypes(VarTypes, !Q) :-
+ !Q ^ qi_vartypes := VarTypes.
+set_warnings(Warnings, !Q) :-
+ !Q ^ qi_warnings := Warnings.
+set_rtti_varmaps(RttiVarMaps, !Q) :-
+ !Q ^ qi_rtti_varmaps := RttiVarMaps.
%-----------------------------------------------------------------------------%
cvs diff: Diffing notes
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list