[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