[m-rev.] for post-commit review: improve performance of ambiguity handling
Zoltan Somogyi
zs at csse.unimelb.edu.au
Mon Jul 31 13:18:51 AEST 2006
Fix a performance problem in the handling of highly overloaded code.
compiler/typecheck_info.m:
We used to record ambiguous overloading situations in a set of
context/info pairs. Since sets are represented as sorted lists,
adding N new situation's records had complexity O(n^2). If N is large,
that can be too slow. (N can be large without causing typecheck.m to
abort if there are lots of disjuncts, each with a tolerable amount
of ambiguity.) From now on, we represent these situations as a map
from overloaded symbols to the unsorted list of of contexts in which
that symbol is used. Since we can add new contexts to the front,
the complexity of the new algorithm is just O(log N), with an
O(n log n) sort at the end.
compiler/typecheck.m:
Use the interface in typecheck_info to record ambiguities.
compiler/typecheck_errors.m:
Use the new format to improve the error messages for ambiguous code:
give the list of possible matches for each ambiguous symbol just once.
tests/warnings/ambiguous_overloading.exp:
Update this expected output file for the now non-redundant error
messages.
Zoltan.
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/typecheck.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/typecheck.m,v
retrieving revision 1.397
diff -u -b -r1.397 typecheck.m
--- compiler/typecheck.m 28 Jul 2006 04:54:02 -0000 1.397
+++ compiler/typecheck.m 30 Jul 2006 10:16:12 -0000
@@ -1528,11 +1528,9 @@
typecheck_call_overloaded_pred(CallId, PredIdList, Args, GoalPath,
!Info, !IO) :-
- typecheck_info_get_overloaded_symbols(!.Info, OverloadedSymbols0),
typecheck_info_get_context(!.Info, Context),
- Symbol = overloaded_symbol(Context, overloaded_pred(CallId, PredIdList)),
- set.insert(OverloadedSymbols0, Symbol, OverloadedSymbols),
- typecheck_info_set_overloaded_symbols(OverloadedSymbols, !Info),
+ Symbol = overloaded_pred(CallId, PredIdList),
+ typecheck_info_add_overloaded_symbol(Symbol, Context, !Info),
% Let the new arg_type_assign_set be the cross-product of the current
% type_assign_set and the set of possible lists of argument types
@@ -1917,13 +1915,10 @@
ConsDefnList = [_]
;
ConsDefnList = [_, _ | _],
- typecheck_info_get_overloaded_symbols(!.Info, OverloadedSymbols0),
typecheck_info_get_context(!.Info, Context),
Sources = list.map(project_cons_type_info_source, ConsDefnList),
- Symbol = overloaded_symbol(Context,
- overloaded_func(Functor, Sources)),
- set.insert(OverloadedSymbols0, Symbol, OverloadedSymbols),
- typecheck_info_set_overloaded_symbols(OverloadedSymbols, !Info)
+ Symbol = overloaded_func(Functor, Sources),
+ typecheck_info_add_overloaded_symbol(Symbol, Context, !Info)
),
% Produce the ConsTypeAssignSet, which is essentially the
Index: compiler/typecheck_errors.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/typecheck_errors.m,v
retrieving revision 1.23
diff -u -b -r1.23 typecheck_errors.m
--- compiler/typecheck_errors.m 27 Jul 2006 05:01:30 -0000 1.23
+++ compiler/typecheck_errors.m 30 Jul 2006 16:27:05 -0000
@@ -377,38 +377,59 @@
FirstSpec = error_msg_spec(yes, Context, 0, InitVerboseWarning),
typecheck_info_get_overloaded_symbols(Info, OverloadedSymbolSet),
- set.to_sorted_list(OverloadedSymbolSet, OverloadedSymbols),
+ map.to_assoc_list(OverloadedSymbolSet, OverloadedSymbols),
+ OverloadedSymbolsSortedContexts =
+ assoc_list.map_values_only(sort_and_remove_dups, OverloadedSymbols),
(
- OverloadedSymbols = [],
+ OverloadedSymbolsSortedContexts = [],
Specs = [FirstSpec]
;
(
- OverloadedSymbols = [_],
+ OverloadedSymbolsSortedContexts = [_ - Contexts],
+ (
+ Contexts = [],
+ unexpected(this_file,
+ "report_warning_too_much_overloading: no contexts")
+ ;
+ Contexts = [_],
SecondSpecPieces =
[words("The following symbol was overloaded"),
words("in the following context."), nl]
;
- OverloadedSymbols = [_, _ | _],
+ Contexts = [_, _ | _],
+ SecondSpecPieces =
+ [words("The following symbol was overloaded"),
+ words("in the following contexts."), nl]
+ )
+ ;
+ OverloadedSymbolsSortedContexts = [_, _ | _],
SecondSpecPieces =
[words("The following symbols were overloaded"),
words("in the following contexts."), nl]
),
SecondSpec = error_msg_spec(no, Context, 0, SecondSpecPieces),
typecheck_info_get_module_info(Info, ModuleInfo),
- DetailSpecs = list.map(describe_overloaded_symbol(ModuleInfo),
- OverloadedSymbols),
+ DetailSpecsList = list.map(describe_overloaded_symbol(ModuleInfo),
+ OverloadedSymbolsSortedContexts),
+ list.condense(DetailSpecsList, DetailSpecs),
Specs = [FirstSpec, SecondSpec | DetailSpecs]
),
record_warning(!IO),
write_error_specs(Specs, !IO).
-:- func describe_overloaded_symbol(module_info, overloaded_symbol)
- = error_msg_spec.
+:- func describe_overloaded_symbol(module_info,
+ pair(overloaded_symbol, list(prog_context))) = list(error_msg_spec).
-describe_overloaded_symbol(ModuleInfo, Symbol) = Spec :-
- Symbol = overloaded_symbol(Context, Info),
+describe_overloaded_symbol(ModuleInfo, Symbol - SortedContexts) = Specs :-
+ (
+ SortedContexts = [],
+ unexpected(this_file, "describe_overloaded_symbol: no context")
+ ;
+ SortedContexts = [FirstContext | LaterContexts],
+ % We print a detailed message for the first context, but omit
+ % repeating the list of possible matches for any later contexts.
(
- Info = overloaded_pred(CallId, PredIds),
+ Symbol = overloaded_pred(CallId, PredIds),
StartPieces = [words("The predicate symbol"),
simple_call_id(CallId), suffix("."), nl,
words("The possible matches are:"), nl_indent_delta(1)],
@@ -416,9 +437,11 @@
should_module_qualify), PredIds),
PredIdPieces = component_list_to_line_pieces(PredIdPiecesList,
[suffix(".")]),
- Pieces = StartPieces ++ PredIdPieces
+ FirstPieces = StartPieces ++ PredIdPieces,
+ LaterPieces = [words("The predicate symbol"),
+ simple_call_id(CallId), words("is also overloaded here.")]
;
- Info = overloaded_func(ConsId, Sources),
+ Symbol = overloaded_func(ConsId, Sources),
( ConsId = cons(SymName, Arity) ->
ConsIdPiece = sym_name_and_arity(SymName / Arity)
;
@@ -427,13 +450,25 @@
StartPieces = [words("The function symbol"), ConsIdPiece,
suffix("."), nl,
words("The possible matches are:"), nl_indent_delta(1)],
- SourcePiecesList = list.map(describe_cons_type_info_source(ModuleInfo),
- Sources),
+ SourcePiecesList = list.map(
+ describe_cons_type_info_source(ModuleInfo), Sources),
SourcePieces = component_list_to_line_pieces(SourcePiecesList,
[suffix(".")]),
- Pieces = StartPieces ++ SourcePieces
+ FirstPieces = StartPieces ++ SourcePieces,
+ LaterPieces = [words("The function symbol"), ConsIdPiece,
+ words("is also overloaded here.")]
),
- Spec = error_msg_spec(no, Context, 0, Pieces).
+ FirstSpec = error_msg_spec(no, FirstContext, 0, FirstPieces),
+ LaterSpecs = list.map(context_to_error_msg_spec(LaterPieces),
+ LaterContexts),
+ Specs = [FirstSpec | LaterSpecs]
+ ).
+
+:- func context_to_error_msg_spec(list(format_component), prog_context)
+ = error_msg_spec.
+
+context_to_error_msg_spec(Pieces, Context) =
+ error_msg_spec(no, Context, 0, Pieces).
:- func describe_cons_type_info_source(module_info, cons_type_info_source)
= list(format_component).
Index: compiler/typecheck_info.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/typecheck_info.m,v
retrieving revision 1.10
diff -u -b -r1.10 typecheck_info.m
--- compiler/typecheck_info.m 20 Apr 2006 05:37:04 -0000 1.10
+++ compiler/typecheck_info.m 30 Jul 2006 10:17:47 -0000
@@ -29,7 +29,7 @@
:- import_module bool.
:- import_module io.
:- import_module list.
-:- import_module set.
+:- import_module map.
%-----------------------------------------------------------------------------%
%
@@ -81,23 +81,20 @@
found_error :: bool,
% Did we find any type errors?
- overloaded_symbols :: set(overloaded_symbol),
- % The set of symbols used by the current
- % predicate that have more than one accessible
- % definition.
+ overloaded_symbols :: overloaded_symbol_map,
+ % The symbols used by the current predicate
+ % that have more than one accessible
+ % definition, mapped to the unsorted list of
+ % the locations that refer to them.
warned_about_overloading :: bool
% Have we already warned about highly
% ambiguous overloading?
).
-:- type overloaded_symbol
- ---> overloaded_symbol(
- prog_context,
- overloaded_symbol_info
- ).
+:- type overloaded_symbol_map == map(overloaded_symbol, list(prog_context)).
-:- type overloaded_symbol_info
+:- type overloaded_symbol
---> overloaded_pred(
simple_call_id,
list(pred_id)
@@ -164,7 +161,7 @@
:- pred typecheck_info_get_warned_about_overloading(typecheck_info::in,
bool::out) is det.
:- pred typecheck_info_get_overloaded_symbols(typecheck_info::in,
- set(overloaded_symbol)::out) is det.
+ overloaded_symbol_map::out) is det.
:- pred typecheck_info_get_pred_import_status(typecheck_info::in,
import_status::out) is det.
@@ -182,7 +179,7 @@
typecheck_info::in, typecheck_info::out) is det.
:- pred typecheck_info_set_warned_about_overloading(bool::in,
typecheck_info::in, typecheck_info::out) is det.
-:- pred typecheck_info_set_overloaded_symbols(set(overloaded_symbol)::in,
+:- pred typecheck_info_set_overloaded_symbols(overloaded_symbol_map::in,
typecheck_info::in, typecheck_info::out) is det.
:- pred typecheck_info_set_pred_import_status(import_status::in,
typecheck_info::in, typecheck_info::out) is det.
@@ -201,6 +198,9 @@
:- pred typecheck_info_get_pred_markers(typecheck_info::in, pred_markers::out)
is det.
+:- pred typecheck_info_add_overloaded_symbol(overloaded_symbol::in,
+ prog_context::in, typecheck_info::in, typecheck_info::out) is det.
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
@@ -344,8 +344,8 @@
:- import_module parse_tree.prog_type_subst.
:- import_module parse_tree.prog_util.
-:- import_module map.
:- import_module pair.
+:- import_module set.
:- import_module svmap.
:- import_module term.
:- import_module varset.
@@ -362,7 +362,7 @@
map.init(ConstraintMap),
FoundTypeError = no,
WarnedAboutOverloading = no,
- set.init(OverloadedSymbols),
+ map.init(OverloadedSymbols),
Info = typecheck_info(ModuleInfo, CallPredId, 0, PredId, Status, Markers,
IsFieldAccessFunction, Context,
unify_context(explicit, []), VarSet,
@@ -577,6 +577,17 @@
module_info_pred_info(ModuleInfo, PredId, PredInfo),
pred_info_get_markers(PredInfo, PredMarkers).
+typecheck_info_add_overloaded_symbol(Symbol, Context, !Info) :-
+ typecheck_info_get_overloaded_symbols(!.Info, SymbolMap0),
+ ( map.search(SymbolMap0, Symbol, OldContexts) ->
+ Contexts = [Context | OldContexts],
+ map.det_update(SymbolMap0, Symbol, Contexts, SymbolMap)
+ ;
+ Contexts = [Context],
+ map.det_insert(SymbolMap0, Symbol, Contexts, SymbolMap)
+ ),
+ typecheck_info_set_overloaded_symbols(SymbolMap, !Info).
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/stream
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
Index: tests/warnings/ambiguous_overloading.exp
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/warnings/ambiguous_overloading.exp,v
retrieving revision 1.4
diff -u -b -r1.4 ambiguous_overloading.exp
--- tests/warnings/ambiguous_overloading.exp 20 Apr 2006 05:37:13 -0000 1.4
+++ tests/warnings/ambiguous_overloading.exp 30 Jul 2006 16:27:46 -0000
@@ -27,32 +27,22 @@
ambiguous_overloading.m:045: `ambiguous_overloading.baz'/0.
ambiguous_overloading.m:055: In clause for predicate `test_lt/1': warning:
ambiguous_overloading.m:055: highly ambiguous overloading.
-ambiguous_overloading.m:055: The following symbols were overloaded in the
+ambiguous_overloading.m:055: The following symbol was overloaded in the
ambiguous_overloading.m:055: following contexts.
ambiguous_overloading.m:050: The predicate symbol predicate `</2'.
ambiguous_overloading.m:050: The possible matches are:
ambiguous_overloading.m:050: predicate `float.</2',
ambiguous_overloading.m:050: predicate `int.</2'.
-ambiguous_overloading.m:051: The predicate symbol predicate `</2'.
-ambiguous_overloading.m:051: The possible matches are:
-ambiguous_overloading.m:051: predicate `float.</2',
-ambiguous_overloading.m:051: predicate `int.</2'.
-ambiguous_overloading.m:052: The predicate symbol predicate `</2'.
-ambiguous_overloading.m:052: The possible matches are:
-ambiguous_overloading.m:052: predicate `float.</2',
-ambiguous_overloading.m:052: predicate `int.</2'.
-ambiguous_overloading.m:053: The predicate symbol predicate `</2'.
-ambiguous_overloading.m:053: The possible matches are:
-ambiguous_overloading.m:053: predicate `float.</2',
-ambiguous_overloading.m:053: predicate `int.</2'.
-ambiguous_overloading.m:054: The predicate symbol predicate `</2'.
-ambiguous_overloading.m:054: The possible matches are:
-ambiguous_overloading.m:054: predicate `float.</2',
-ambiguous_overloading.m:054: predicate `int.</2'.
-ambiguous_overloading.m:055: The predicate symbol predicate `</2'.
-ambiguous_overloading.m:055: The possible matches are:
-ambiguous_overloading.m:055: predicate `float.</2',
-ambiguous_overloading.m:055: predicate `int.</2'.
+ambiguous_overloading.m:051: The predicate symbol predicate `</2' is also
+ambiguous_overloading.m:051: overloaded here.
+ambiguous_overloading.m:052: The predicate symbol predicate `</2' is also
+ambiguous_overloading.m:052: overloaded here.
+ambiguous_overloading.m:053: The predicate symbol predicate `</2' is also
+ambiguous_overloading.m:053: overloaded here.
+ambiguous_overloading.m:054: The predicate symbol predicate `</2' is also
+ambiguous_overloading.m:054: overloaded here.
+ambiguous_overloading.m:055: The predicate symbol predicate `</2' is also
+ambiguous_overloading.m:055: overloaded here.
ambiguous_overloading.m:071: In clause for predicate `set_browser_param_from_option_table/3':
ambiguous_overloading.m:071: warning: highly ambiguous overloading.
ambiguous_overloading.m:071: The following symbol was overloaded in the
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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