[m-rev.] diff: map.merge/3 and duplicate keys
Julien Fischer
juliensf at csse.unimelb.edu.au
Wed Sep 6 17:39:46 AEST 2006
Estimated hours taken: 1.5
Branches: main, release
Change the implementation of map.merge/3 so that it throws an exception if the
sets of keys of the input maps are not disjoint. This is more in keeping with
the documentation for that predicate which says they should be disjoint.
The existing implementation handled duplicate keys by inserting the key and
the smallest of the corresponding values into the output map. Some of the
code in the compiler seems to rely on this behaviour - this is (probably) a
bug but in at least in one instance, to do with merging RTTI varmaps
during higher-order specialisation, it's going to be a bit tricky to fix.
Rather than modify the compiler at the moment the old version of map.merge/3
is available as map.old_merge/3 and the compiler still uses this. (This
predicate is not included in the library reference manual.)
library/map.m:
Make map.merge/3 throw an exception if the sets of keys of the
input maps are not disjoint.
Add the implementor-only predicate map.old_merge/3 for use by the
compiler.
compiler/hlds_rtti.m:
compiler/interval.m:
compiler/prog_io.m:
compiler/tupling.m:
Conform to the above changes.
tests/hard_coded/map_merge_test.{m,exp}:
Test for the new behaviour.
tests/hard_coded/Makefile:
Don't run the above test in deep profiling grades since it
catches exceptions which the deep profiler cannot currently handle.
Julien.
(NOTE: the following diff is against the 0.13 branch)
Index: compiler/hlds_rtti.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_rtti.m,v
retrieving revision 1.3
diff -u -r1.3 hlds_rtti.m
--- compiler/hlds_rtti.m 29 Mar 2006 08:06:49 -0000 1.3
+++ compiler/hlds_rtti.m 6 Sep 2006 05:18:01 -0000
@@ -656,8 +656,8 @@
% On the other hand, we insist that this information is consistent.
%
- map.merge(TypeMapA, TypeMapB, TypeMap),
- map.merge(ConstraintMapA, ConstraintMapB, ConstraintMap),
+ map.old_merge(TypeMapA, TypeMapB, TypeMap),
+ map.old_merge(ConstraintMapA, ConstraintMapB, ConstraintMap),
VarMaps = rtti_varmaps(TCImap, TImap, TypeMap, ConstraintMap).
Index: compiler/interval.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/interval.m,v
retrieving revision 1.16
diff -u -r1.16 interval.m
--- compiler/interval.m 29 Mar 2006 08:06:52 -0000 1.16
+++ compiler/interval.m 6 Sep 2006 05:13:26 -0000
@@ -1036,7 +1036,7 @@
create_shadow_vars(ArgVars, VarsToExtract, VarSet0, VarSet,
VarTypes0, VarTypes, map.init, NewRename, map.init, VoidRename),
!:VarInfo = var_info(VarSet, VarTypes),
- map.merge(!.VarRename, NewRename, !:VarRename),
+ map.old_merge(!.VarRename, NewRename, !:VarRename),
% We rename the original goal
rename_vars_in_goal(!.VarRename, Goal2, Goal3),
rename_vars_in_goal(VoidRename, Goal3, Goal)
Index: compiler/prog_io.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/prog_io.m,v
retrieving revision 1.264.2.1
diff -u -r1.264.2.1 prog_io.m
--- compiler/prog_io.m 15 Aug 2006 06:24:50 -0000 1.264.2.1
+++ compiler/prog_io.m 6 Sep 2006 05:25:44 -0000
@@ -2972,7 +2972,7 @@
combine_quantifier_results(ok(UnivConstraints, InstConstraints0),
ok(ExistConstraints, InstConstraints1), ExistQVars,
ok(ExistQVars, constraints(UnivConstraints, ExistConstraints),
- InstConstraints0 `map.merge` InstConstraints1)).
+ InstConstraints0 `map.old_merge` InstConstraints1)).
:- pred get_quant_vars(quantifier_type::in, module_name::in,
decl_attrs::in, decl_attrs::out, list(var)::in, list(var)::out) is det.
@@ -3014,7 +3014,7 @@
combine_constraint_list_results(error(Msg, Term), _, error(Msg, Term)).
combine_constraint_list_results(ok(_, _), error(Msg, Term), error(Msg, Term)).
combine_constraint_list_results(ok(CC0, IC0), ok(CC1, IC1),
- ok(CC0 ++ CC1, IC0 `map.merge` IC1)).
+ ok(CC0 ++ CC1, IC0 `map.old_merge` IC1)).
:- pred get_existential_constraints_from_term(module_name::in,
term::in, term::out, maybe1(list(prog_constraint))::out) is det.
Index: compiler/tupling.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/tupling.m,v
retrieving revision 1.22.2.1
diff -u -r1.22.2.1 tupling.m
--- compiler/tupling.m 7 Aug 2006 05:02:35 -0000 1.22.2.1
+++ compiler/tupling.m 6 Sep 2006 05:29:36 -0000
@@ -475,7 +475,7 @@
% Only include this variable in the list of candidates if there are two
% or more procedures in the SCC with head variables having the same name.
( ListOfOrigins = [_, _ | _] ->
- list.foldl(map.merge, ListOfOrigins, map.init, Origins),
+ list.foldl(map.old_merge, ListOfOrigins, map.init, Origins),
CandidateHeadVars = CandidateHeadVars0 ++ [HeadVarName - Origins]
;
CandidateHeadVars = CandidateHeadVars0
@@ -702,7 +702,7 @@
RenameMapB, ProcStartInsert),
rename_vars_in_goal(RenameMapB, Goal2, Goal3),
- map.merge(RenameMapA, RenameMapB, RenameMap),
+ map.old_merge(RenameMapA, RenameMapB, RenameMap),
apply_headvar_correction(set.from_list(HeadVars), RenameMap, Goal3, Goal),
proc_info_set_goal(Goal, !ProcInfo),
proc_info_set_varset(VarSet, !ProcInfo),
Index: library/map.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.103
diff -u -r1.103 map.m
--- library/map.m 29 Mar 2006 08:07:44 -0000 1.103
+++ library/map.m 6 Sep 2006 07:29:21 -0000
@@ -236,9 +236,9 @@
:- func map.from_corresponding_lists(list(K), list(V)) = map(K, V).
:- pred map.from_corresponding_lists(list(K)::in, list(V)::in, map(K, V)::out)
is det.
-
- % For map.merge(MapA, MapB, Map), MapA and MapB must not both contain
- % the same key.
+
+ % Merge the contents of the two maps.
+ % Throws an exception of both sets of keys are not disjoint.
%
:- func map.merge(map(K, V), map(K, V)) = map(K, V).
:- pred map.merge(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.
@@ -469,6 +469,20 @@
:- import_module tree234.
:- type map(K, V) == tree234(K, V).
+
+%-----------------------------------------------------------------------------%
+
+% Note to implementors:
+%
+% This is the old version of map.merge/3. It is buggy in the sense that if the
+% sets of keys of the input maps are not disjoint it won't throw an exception
+% but will insert the key and the smallest of the two corresponding values to
+% the output map. Eventually we would like to get rid of this version but some
+% of the code in the compiler currently assumes this behaviour and fixing it is
+% non-trivial.
+
+:- func map.old_merge(map(K, V), map(K, V)) = map(K, V).
+:- pred map.old_merge(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.
%-----------------------------------------------------------------------------%
@@ -725,6 +739,14 @@
map.to_assoc_list(M0, ML0),
map.to_assoc_list(M1, ML1),
list.merge(ML0, ML1, ML),
+ M = map.det_insert_from_assoc_list(map.init, ML).
+
+%-----------------------------------------------------------------------------%
+
+map.old_merge(M0, M1, M) :-
+ map.to_assoc_list(M0, ML0),
+ map.to_assoc_list(M1, ML1),
+ list.merge(ML0, ML1, ML),
map.from_sorted_assoc_list(ML, M).
%-----------------------------------------------------------------------------%
@@ -1056,6 +1078,9 @@
map.merge(M1, M2) = M3 :-
map.merge(M1, M2, M3).
+map.old_merge(M1, M2) = M3 :-
+ map.old_merge(M1, M2, M3).
+
map.overlay(M1, M2) = M3 :-
map.overlay(M1, M2, M3).
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.282.2.5
diff -u -r1.282.2.5 Mmakefile
--- tests/hard_coded/Mmakefile 28 Aug 2006 14:02:35 -0000 1.282.2.5
+++ tests/hard_coded/Mmakefile 6 Sep 2006 06:35:39 -0000
@@ -410,6 +410,7 @@
allow_stubs \
backend_external \
dir_test \
+ map_merge_test \
test_array2d \
test_injection \
user_defined_equality \
Index: tests/hard_coded/map_merge_test.exp
===================================================================
RCS file: tests/hard_coded/map_merge_test.exp
diff -N tests/hard_coded/map_merge_test.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/map_merge_test.exp 6 Sep 2006 06:34:54 -0000
@@ -0,0 +1 @@
+SUCCESS
\ No newline at end of file
Index: tests/hard_coded/map_merge_test.m
===================================================================
RCS file: tests/hard_coded/map_merge_test.m
diff -N tests/hard_coded/map_merge_test.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/map_merge_test.m 6 Sep 2006 06:34:54 -0000
@@ -0,0 +1,37 @@
+% vim: ft=mercury ts=4 sw=4 et
+%
+% Check that map.merge/3 throws an exception if the sets of keys
+% are not disjoint.
+
+:- module map_merge_test.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+:- implementation.
+
+:- import_module assoc_list.
+:- import_module exception.
+:- import_module list.
+:- import_module map.
+:- import_module pair.
+:- import_module unit.
+
+main(!IO) :-
+ try_io(main_2, Result, !IO),
+ (
+ Result = succeeded(_),
+ io.write_string("FAILURE", !IO)
+ ;
+ Result = exception(_),
+ io.write_string("SUCCESS", !IO)
+ ).
+
+:- pred main_2(map(int, int)::out, io::di, io::uo) is det.
+
+main_2(MapC, !IO) :-
+ MapA = map.from_assoc_list([10 - 10, 20 - 20, 30 - 30]),
+ MapB = map.from_assoc_list([5 - 5, 20 - 20, 35 - 35]),
+ map.merge(MapA, MapB, MapC).
--------------------------------------------------------------------------
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