diff: allow mixing cc and non-cc modes

[Fergus Henderson]

Estimated hours taken: 3

Allow a predicate to have matching `cc' and `non-cc' modes.

compiler/det_analysis.m:
	If there is a call to a cc procedure in a non-cc context,
	then search for a mode of that predicate which is
	identical to the called mode except that it is not cc.
	If such a mode is found, use it, rather than reporting
	an error.

compiler/modecheck_call.m:
	Add predicate modes_are_identical_bar_cc, for use by
	det_analysis.m.

NEWS:
LIMITATIONS:
doc/reference_manual.texi:
	Document the new feature and delete documentation about the
	lack of this feature.

tests/hard_coded/Mmakefile:
tests/hard_coded/cc_and_non_cc_test.m:
tests/hard_coded/cc_and_non_cc_test.exp:
	Add a test case for the new feature.

Index: LIMITATIONS
===================================================================
RCS file: /home/mercury1/repository/mercury/LIMITATIONS,v
retrieving revision 1.12
diff -u -r1.12 LIMITATIONS
--- LIMITATIONS	1997/10/15 07:39:27	1.12
+++ LIMITATIONS	1998/05/30 15:00:28
@@ -10,9 +10,6 @@
 * The compiler does not yet use structure reuse or compile-time
   garbage collection to exploit unique modes :-(
 
-* It is not possible to give both `cc_multi' and `multi' (or `cc_nondet'
-  and `nondet') determinisms for the same mode of a predicate.
-
 * Type inference and mode inference are a bit imperfect.
 
 We are working on eliminating all of these problems. 
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.103
diff -u -r1.103 NEWS
--- NEWS	1998/05/29 21:41:55	1.103
+++ NEWS	1998/05/30 15:09:58
@@ -246,6 +246,12 @@
 * Mode inference can now infer "mostly-unique" modes as well as
   "unique" modes.
 
+* You can now declare both committed-choice ("cc") and backtracking (non-cc)
+  modes for the same predicate.
+  
+  Determinism analysis will pick the appropriate one to use for each
+  call based on the context.
+
 * The module system now includes support for sub-modules.
 
   The aim of this extension is twofold.  One aim is to provide more
Index: compiler/det_analysis.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/det_analysis.m,v
retrieving revision 1.131
diff -u -r1.131 det_analysis.m
--- det_analysis.m	1998/05/15 07:07:03	1.131
+++ det_analysis.m	1998/05/30 14:56:14
@@ -103,9 +103,9 @@
 :- implementation.
 
 :- import_module hlds_goal, prog_data, det_report, det_util.
-:- import_module type_util, mode_util, options, passes_aux.
+:- import_module type_util, modecheck_call, mode_util, options, passes_aux.
 :- import_module hlds_out, mercury_to_mercury, instmap.
-:- import_module bool, map, set, require, term.
+:- import_module assoc_list, bool, map, set, require, term.
 
 %-----------------------------------------------------------------------------%
 
@@ -425,10 +425,10 @@
 	% This is the point at which annotations start changing
 	% when we iterate to fixpoint for global determinism inference.
 
-det_infer_goal_2(call(PredId, ModeId, A, B, C, N), GoalInfo, _, SolnContext,
+det_infer_goal_2(call(PredId, ModeId0, A, B, C, N), GoalInfo, _, SolnContext,
 		DetInfo, _, _,
 		call(PredId, ModeId, A, B, C, N), Detism, Msgs) :-
-	det_lookup_detism(DetInfo, PredId, ModeId, Detism0),
+	det_lookup_detism(DetInfo, PredId, ModeId0, Detism0),
 	%
 	% Make sure we don't try to call a committed-choice pred
 	% from a non-committed-choice context.
@@ -438,14 +438,26 @@
 		NumSolns = at_most_many_cc,
 		SolnContext \= first_soln
 	->
-		Msgs = [cc_pred_in_wrong_context(GoalInfo, Detism0,
-				PredId, ModeId)],
-		% Code elsewhere relies on the assumption that
-		% SolnContext \= first_soln => NumSolns \= at_most_many_cc,
-		% so we need to enforce that here.
-		determinism_components(Detism, CanFail, at_most_many)
+		(
+			det_find_matching_non_cc_mode(DetInfo, PredId, ModeId0,
+				ModeId1)
+		->
+			ModeId = ModeId1,
+			Msgs = [],
+			Detism = Detism0
+		;
+			Msgs = [cc_pred_in_wrong_context(GoalInfo, Detism0,
+					PredId, ModeId0)],
+			ModeId = ModeId0,
+			% Code elsewhere relies on the assumption that
+			%	SolnContext \= first_soln =>
+			%		NumSolns \= at_most_many_cc,
+			% so we need to enforce that here.
+			determinism_components(Detism, CanFail, at_most_many)
+		)
 	;
 		Msgs = [],
+		ModeId = ModeId0,
 		Detism = Detism0
 	).
 
@@ -752,6 +764,46 @@
 	det_infer_switch(Cases0, InstMap0, SolnContext, DetInfo, CanFail2,
 		MaxSolns2, Cases, Detism, Msgs2),
 	list__append(Msgs1, Msgs2, Msgs).
+
+%-----------------------------------------------------------------------------%
+
+	% det_find_matching_non_cc_mode(DetInfo, PredId, ProcId0, ProcId):
+	%	Search for a mode of the given predicate that
+	% 	is identical to the mode ProcId0, except that its
+	%	determinism is non-cc whereas ProcId0's detism is cc.
+	%	Let ProcId be the first such mode.
+
+:- pred det_find_matching_non_cc_mode(det_info, pred_id, proc_id, proc_id).
+:- mode det_find_matching_non_cc_mode(in, in, in, out) is semidet.
+
+det_find_matching_non_cc_mode(DetInfo, PredId, ProcId0, ProcId) :-
+	det_info_get_module_info(DetInfo, ModuleInfo),
+        module_info_preds(ModuleInfo, PredTable),
+	map__lookup(PredTable, PredId, PredInfo),
+	pred_info_procedures(PredInfo, ProcTable),
+	map__to_assoc_list(ProcTable, ProcList),
+	det_find_matching_non_cc_mode_2(ProcList, ModuleInfo, PredInfo,
+		ProcId0, ProcId).
+
+:- pred det_find_matching_non_cc_mode_2(assoc_list(proc_id, proc_info),
+		module_info, pred_info, proc_id, proc_id).
+:- mode det_find_matching_non_cc_mode_2(in, in, in, in, out) is semidet.
+
+det_find_matching_non_cc_mode_2([ProcId1 - ProcInfo | Rest],
+		ModuleInfo, PredInfo, ProcId0, ProcId) :-
+	(
+		ProcId1 \= ProcId0,
+		proc_info_interface_determinism(ProcInfo, Detism),
+		determinism_components(Detism, _CanFail, MaxSoln),
+		MaxSoln = at_most_many,
+		modes_are_identical_bar_cc(ProcId0, ProcId1, PredInfo,
+			ModuleInfo)
+	->
+		ProcId = ProcId1
+	;
+		det_find_matching_non_cc_mode_2(Rest, ModuleInfo, PredInfo,
+				ProcId0, ProcId)
+	).
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/modecheck_call.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/modecheck_call.m,v
retrieving revision 1.24
diff -u -r1.24 modecheck_call.m
--- modecheck_call.m	1998/03/03 17:35:17	1.24
+++ modecheck_call.m	1998/05/30 15:20:21
@@ -52,10 +52,23 @@
 	% they are indistinguishable; that is, whether any valid call to
 	% one mode would also be a valid call to the other.
 	% (If so, it is a mode error.)
+	% Note that mode declarations which only have different final insts
+	% do not count as distinguishable.
 	%
 :- pred modes_are_indistinguishable(proc_id, proc_id, pred_info, module_info).
 :- mode modes_are_indistinguishable(in, in, in, in) is semidet.
 
+	%
+	% Given two modes of a predicate, figure out whether
+	% they are identical, except that one is cc_nondet/cc_multi
+	% and the other is nondet/multi.
+	% This is used by determinism analysis to substitute
+	% a multi mode for a cc_multi one if the call occurs in a
+	% non-cc context.
+	%
+:- pred modes_are_identical_bar_cc(proc_id, proc_id, pred_info, module_info).
+:- mode modes_are_identical_bar_cc(in, in, in, in) is semidet.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -444,8 +457,11 @@
 	% they are indistinguishable; that is, whether any valid call to
 	% one mode would also be a valid call to the other.
 	% (If so, it is a mode error.)
+	% Note that mode declarations which only have different final insts
+	% do not count as distinguishable.
 	%
-	% The code for this is similar to the code for compare_procs/5 below.
+	% The code for this is similar to the code for
+	% modes_are_indentical/4 and compare_proc/5 below.
 	%
 modes_are_indistinguishable(ProcId, OtherProcId, PredInfo, ModuleInfo) :-
 	pred_info_procedures(PredInfo, Procs),
@@ -487,6 +503,64 @@
 
 %-----------------------------------------------------------------------------%
 
+	%
+	% Given two modes of a predicate, figure out whether
+	% they are identical, except that one is cc_nondet/cc_multi
+	% and the other is nondet/multi.
+	%
+	% The code for this is similar to the code for compare_proc/5 below
+	% and modes_are_indistinguishable/4 above.
+	%
+modes_are_identical_bar_cc(ProcId, OtherProcId, PredInfo, ModuleInfo) :-
+	pred_info_procedures(PredInfo, Procs),
+	map__lookup(Procs, ProcId, ProcInfo),
+	map__lookup(Procs, OtherProcId, OtherProcInfo),
+
+	%
+	% Compare the initial insts of the arguments
+	%
+	proc_info_argmodes(ProcInfo, ProcArgModes),
+	proc_info_argmodes(OtherProcInfo, OtherProcArgModes),
+	mode_list_get_initial_insts(ProcArgModes, ModuleInfo, InitialInsts),
+	mode_list_get_initial_insts(OtherProcArgModes, ModuleInfo,
+							OtherInitialInsts),
+	compare_inst_list(InitialInsts, OtherInitialInsts, no,
+		CompareInitialInsts, ModuleInfo),
+	CompareInitialInsts = same,
+
+	%
+	% Compare the final insts of the arguments
+	%
+	mode_list_get_final_insts(ProcArgModes, ModuleInfo, FinalInsts),
+	mode_list_get_final_insts(OtherProcArgModes, ModuleInfo,
+							OtherFinalInsts),
+	compare_inst_list(FinalInsts, OtherFinalInsts, no,
+		CompareFinalInsts, ModuleInfo),
+	CompareFinalInsts = same,
+
+	%
+	% Compare the expected livenesses of the arguments
+	%
+	get_arg_lives(ProcArgModes, ModuleInfo, ProcArgLives),
+	get_arg_lives(OtherProcArgModes, ModuleInfo, OtherProcArgLives),
+	compare_liveness_list(ProcArgLives, OtherProcArgLives, CompareLives),
+	CompareLives = same,
+
+	%
+	% Compare the determinisms, ignoring the cc part.
+	%
+	proc_info_interface_determinism(ProcInfo, Detism),
+	proc_info_interface_determinism(OtherProcInfo, OtherDetism),
+	determinism_components(Detism, CanFail, Solns),
+	determinism_components(OtherDetism, OtherCanFail, OtherSolns),
+	CanFail = OtherCanFail,
+	( Solns = OtherSolns
+	; Solns = at_most_many_cc, OtherSolns = at_most_many
+	; Solns = at_most_many, OtherSolns = at_most_many_cc
+	).
+
+%-----------------------------------------------------------------------------%
+
 /*
 The algorithm for choose_best_match is supposed to be equivalent
 to the following specification:
@@ -556,7 +630,8 @@
 	% for calls which could match either mode.
 	%
 	% The code for this is similar to the code for
-	% modes_are_indistiguisable/4 above.
+	% modes_are_indistinguishable/4 and
+	% modes_are_identical_bar_cc/4 above.
 	%
 :- pred compare_proc(proc_id, proc_id, list(var), match, proc_table, mode_info).
 :- mode compare_proc(in, in, in, out, in, mode_info_ui) is det.
Index: doc/reference_manual.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/reference_manual.texi,v
retrieving revision 1.94
diff -u -r1.94 reference_manual.texi
--- reference_manual.texi	1998/05/29 19:29:09	1.94
+++ reference_manual.texi	1998/05/30 15:19:51
@@ -1947,6 +1947,15 @@
 The compiler will check that all calls to a committed-choice
 mode of a predicate do indeed occur in a single-solution context.
 
+You can declare two different modes of a predicate which differ
+only in ``cc-ness'' (i.e. one being @samp{multi} and the other
+ at samp{cc_multi}, or one being @samp{nondet} and the other {cc_nondet}).
+In that case, the compiler will select the appropriate one for each
+call depending on whether the call comes from a single-solution context
+or not.  Calls from single-solution contexts will call the committed
+choice version, while calls which are not from single-solution contexts
+will call the backtracking version.
+
 There are several reasons to use committed choice determinism annotations.
 One reason is for efficiency: committed choice annotations allow
 the compiler to generate much more efficient code.
@@ -1955,12 +1964,6 @@
 Another is for dealing with types that use non-canonical representations
 (@pxref{Equality preds}).
 And there are a variety of other applications.
-
-It would be nice to be able to declare a mode of a predicate as
-both @samp{multi} and @samp{cc_multi}, and have the compiler call
-the appropriate one depending on whether the call comes from a
-single-solution context or not.  However, the current implementation
-does not yet support this.
 
 @node Equality preds
 @chapter User-defined equality predicates
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.30
diff -u -r1.30 Mmakefile
--- Mmakefile	1998/05/27 04:00:51	1.30
+++ Mmakefile	1998/05/30 15:15:29
@@ -13,6 +13,7 @@
 	boyer \
 	c_write_string \
 	cc_nondet_disj \
+	cc_and_non_cc_test \
 	common_type_cast \
 	construct \
 	curry \
cvs diff: tests/hard_coded/cc_and_non_cc_test.exp is a new entry, no comparison available
cvs diff: tests/hard_coded/cc_and_non_cc_test.m is a new entry, no comparison available

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.