[m-rev.] for review: divide and query search for declarative debugger

[Mark Brown]

On 21-Dec-2004, Ian MacLarty <maclarty at cs.mu.OZ.AU> wrote:
> For review by Zoltan and/or Mark. Documentation for review by anyone.
> 
> Estimated hours taken: 80
> Branches: main
> 
> Add divide and query search strategy to declarative debugger.  This version of
> divide and query uses the number of descendent events as a weighting instead of
> the number of descendent nodes, mainly because this is easy to compute when
> portions of the annotated trace are not materialized.

...

> trace/mercury_trace_declarative.h
> trace/mercury_trace_declarative.c
> 	Record REDO event numbers.
> 
> 	Add some functions to set the default search mode by calling the
> 	predicate exported from declarative_debugger.m
> 
> 	Add a function to check in a search mode argument string is valid.

s/in a/that the/

> Index: browser/declarative_analyser.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_analyser.m,v
> retrieving revision 1.17
> diff -u -r1.17 declarative_analyser.m
> --- browser/declarative_analyser.m	16 Dec 2004 00:12:38 -0000	1.17
> +++ browser/declarative_analyser.m	21 Dec 2004 10:48:05 -0000
> @@ -188,6 +214,12 @@
>  				% oracle.
>  			search_mode		:: search_mode,
>  				
> +				% The search mode to use by default. 
> +				% This uses a different type since only
> +				% non-parametized search modes can sensibly be

s/parametized/parametrized/

I think it would be clearer to use the same type for both, and leave it
as an invariant that the default mode would only take certain values.
Then you wouldn't need the 'search_mode_from_default' function below.

> +				% used as the default search mode.
> +			default_search_mode	:: default_search_mode,
> +
>  				% Everytime a search finds a suspect to
>  				% ask the oracle about it is put in this field
>  				% before asking the oracle, so the analyser
> @@ -337,15 +382,14 @@
>  		edt_question(!.Analyser ^ io_action_map, Store, Node,
>  			Question),
>  		Response = revise(Question),
> -		revise_root(SearchSpace, SearchSpace1),
> +		revise_root(Store, SearchSpace, SearchSpace1),
>  		!:Analyser = !.Analyser ^ search_space := SearchSpace1,
>  		!:Analyser = !.Analyser ^ last_search_question := yes(RootId),
> -		!:Analyser = !.Analyser ^ search_mode := top_down
> +		set_default_search_mode(!.Analyser ^ default_search_mode,
> +			!Analyser)

That's a little confusing, since it looks like the above call should be
a no-op.  Perhaps add a new predicate set_search_mode_to_default/2 which
just moves the default search mode into the current search mode.  This
new predicate could be called from set_default_search_mode/3, since that
predicate also sets the current search mode.

>  	;
> -		%
>  		% There must be a root, since a bug was found (and is now
>  		% being revised).
> -		%
>  		throw(internal_error("revise_analysis", "no root"))
>  	).
>  
> @@ -354,6 +398,9 @@
>  	is det <= mercury_edt(S, T).
>  
>  decide_analyser_response(Store, Response, !Analyser) :-
> +	% Check an invarients that should hold for the search space.

s/an invarients that should hold/the invariants/

In any case this comment is redundant, since the documentation for
check_search_space_consistency already describes what it does.  If you want
to put a comment here it should state why you do the sanity check here --
that is, mention what could have gone wrong.

> +	check_search_space_consistency(Store, !.Analyser ^ search_space,
> +		"Start of decide_analyser_response"),
>  	some [!SearchSpace] (
>  		!:SearchSpace = !.Analyser ^ search_space,
>  		(
> @@ -409,7 +457,11 @@
>  				)
>  			)
>  		)
> -	).
> +	),
> +	% Check an invarients that should hold for the search space.

Same comment applies here as above.

> +	check_search_space_consistency(Store, !.Analyser ^ search_space,
> +		"End of decide_analyser_response").
> +
>  
>  :- pred handle_search_response(S::in, search_response::in, 
>  	analyser_state(T)::in, analyser_state(T)::out, 
> @@ -810,3 +871,143 @@
>  			OuterTop, OuterBottom, InnerTop - 1, InnerBottom + 1,
>  			Unknown)
>  	).	
> +
> +:- pred divide_and_query_search(S::in, search_space(T)::in, 
> +	search_space(T)::out, search_response::out, search_mode::out) is det
> +	<= mercury_edt(S, T).
> +
> +divide_and_query_search(Store, !SearchSpace, Response, NewMode) :-
> +	%
> +	% If there's no root yet (because the oracle hasn't asserted any nodes
> +	% are erroneous yet), then use top-down search.
> +	%
> +	(
> +		root(!.SearchSpace, RootId)
> +	->
> +		NewMode = divide_and_query,
> +		(
> +			children(Store, RootId, !SearchSpace, Children)
> +		->
> +			find_middle_weight(Store, Children, RootId, no,
> +				!SearchSpace, Response)
> +		;
> +			Response = require_explicit_subtree(RootId)
> +		)
> +	;
> +		top_down_search(Store, !SearchSpace, Response),
> +		NewMode = divide_and_query
> +	).
> +
> +	% find_middle_weight(Store, SuspectIds, TopId, MaybeLastUnknown,
> +	%	!SearchSpace, Response).
> +	% Find the suspect that splits the portion of the search space rooted
> +	% at TopId into roughly equal portions by weight.  SuspectIds is 

Don't use "roughly"; be more specific about the meaning of this predicate.
For example, you could add the sentence:

	The weight of the chosen suspect will be as close to half the
	weight of TopId as any other suspect being considered.

> +	% a list of suspects who's descendents should be searched.  

s/who's/whose/

> +	% MaybeLastUnknown is the last node that was unknown in the search (
> +	% if any).

That line break should go before the open parenthesis.

> +	%
> +:- pred find_middle_weight(S::in, list(suspect_id)::in, suspect_id::in,
> +	maybe(suspect_id)::in, search_space(T)::in, 
> +	search_space(T)::out, search_response::out)
> +	is det <= mercury_edt(S, T).
> +
> +find_middle_weight(Store, [], _, MaybeLastUnknown, !SearchSpace, Response) :-
> +	(
> +		MaybeLastUnknown = yes(LastUnknown),
> +		Response = question(LastUnknown)
> +	;
> +		MaybeLastUnknown = no,
> +		% This could happen when there were no unknown suspects 
> +		% encountered during the search, in which case we revert 
> +		% to top-down search.
> +		top_down_search(Store, !SearchSpace, Response)
> +	).
> +find_middle_weight(Store, [SuspectId | SuspectIds], TopId, MaybeLastUnknown, 
> +		!SearchSpace, Response) :-
> +	Target = get_weight(!.SearchSpace, TopId) // 2,
> +	%
> +	% Find the heaviest suspect:
> +	%
> +	Weight = get_weight(!.SearchSpace, SuspectId),
> +	list.foldl(max_weight(!.SearchSpace), SuspectIds, 
> +		{Weight, SuspectId}, {MaxWeight, Heaviest}),
> +	(
> +		MaxWeight > Target
> +	->
> +		(
> +			children(Store, Heaviest, !SearchSpace, Children)
> +		->
> +			(
> +				suspect_unknown(!.SearchSpace, Heaviest)
> +			->
> +				NewMaybeLastUnknown = yes(Heaviest)
> +			;
> +				NewMaybeLastUnknown = MaybeLastUnknown
> +			),
> +			find_middle_weight(Store, Children, TopId,
> +				NewMaybeLastUnknown, !SearchSpace, Response)
> +		;
> +			Response = require_explicit_subtree(Heaviest)
> +		)

Note that this if-then-else is quite similar to one in divide_and_query_search
and one below.  The code would be simpler to read if you factor out the common
code.  (This may require an extra map__search in the case that an explicit
subtree is required, but readability is arguably more valuable than efficiency
in this case.)

> +	;
> +		(
> +			suspect_unknown(!.SearchSpace, Heaviest)
> +		->
> +			Response = question(Heaviest)
> +		;
> +			(
> +				MaybeLastUnknown = yes(LastUnknown),
> +				Response = question(LastUnknown)
> +			;
> +				MaybeLastUnknown = no,
> +				% Look deeper until we find an unknown:
> +				(
> +					children(Store, Heaviest, !SearchSpace, 						Children)

There should be a line break in there.

> +				->
> +					find_middle_weight(Store, Children, 
> +						TopId, no, !SearchSpace,
> +						Response)
> +				;
> +					Response = require_explicit_subtree(
> +						Heaviest)
> +				)
> +			)
> +		)		
> +	).
> +
> +:- pred max_weight(search_space(T)::in, suspect_id::in, 
> +	{int, suspect_id}::in, {int, suspect_id}::out) 
> +	is det.
> +
> +max_weight(SearchSpace, SuspectId, {PrevMax, PrevSuspectId},
> +	{NewMax, NewSuspectId}) :-
> +	Weight = get_weight(SearchSpace, SuspectId),
> +	(
> +		Weight > PrevMax
> +	->
> +		NewMax = Weight,
> +		NewSuspectId = SuspectId
> +	;
> +		NewMax = PrevMax,
> +		NewSuspectId = PrevSuspectId
> +	).
> +
> +	% Start doing a default search of the search space.
> +	%
> +:- pred start_default_search(default_search_mode::in, S::in, 
> +	search_space(T)::in, search_space(T)::out,
> +	search_response::out, search_mode::out) is det <= mercury_edt(S, T).

For consistency, the argument order for this predicate should match that of
search/6 (if you still need this predicate after addressing my above remarks).

> +
> +start_default_search(DefaultSearchMode, Store, !SearchSpace, SearchResponse, 
> +		NewMode) :-
> +	(
> +		DefaultSearchMode = top_down,
> +		top_down_search(Store, !SearchSpace, 
> +			SearchResponse),
> +		NewMode = top_down
> +	;
> +		DefaultSearchMode = divide_and_query,
> +		divide_and_query_search(Store, 
> +			!SearchSpace, SearchResponse,
> +			NewMode)
> +	).
> Index: browser/declarative_edt.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_edt.m,v
> retrieving revision 1.2
> diff -u -r1.2 declarative_edt.m
> --- browser/declarative_edt.m	16 Dec 2004 00:12:38 -0000	1.2
> +++ browser/declarative_edt.m	21 Dec 2004 11:25:52 -0000
> @@ -126,7 +126,21 @@
>  		% True if it is not possible to materialize any nodes 
>  		% above the given node.
>  		%
> -	pred edt_topmost_node(S::in, T::in) is semidet
> +	pred edt_topmost_node(S::in, T::in) is semidet,
> + 
> + 		% edt_weight(Store, Node, Weight, ExcessWeight).
> +		% True if Weight is the weight of Node.  ExcessWeight is
> +		% some extra weight that should be added to the ancestors of
> +		% Node because the sum of the weights of the Node and its
> +		% siblings might otherwise be bigger than Node's parent's 
> +		% weight.  For example if the number of events in descendent
> +		% nodes is being used as a weight, then for a FAIL node
> +		% some events may be repeated in siblings of the FAIL node.
> +		% In this case the number of duplicate events should be
> +		% returned in ExcessWeight so they can be added to the
> +		% ancestors.
> + 		%
> + 	pred edt_weight(S::in, T::in, int::out, int::out) is det

The concept of the weight of a node needs to be specified clearly -- I suggest
you add to the comments at the top of this file.  In these comments you should
also delineate any invariants that are assumed by the implementation (e.g.
by the new code in declarative_analyser.m), in particular that the weight
of a node must not be exceeded by the combined weight of its children.

>  ].
>  
>  :- type subterm_mode
> @@ -237,8 +252,8 @@
>  
>  	% Marks the suspect correct and alls its decendents as pruned.
>  	%
> -:- pred assert_suspect_is_correct(suspect_id::in, search_space(T)::in,
> -	search_space(T)::out) is det.
> +:- pred assert_suspect_is_correct(suspect_id::in, 
> +	search_space(T)::in, search_space(T)::out) is det.
>  
>  	% Marks the supect erroneous and marks the complement of the subtree
>  	% rooted at the erroneous suspect as in_erroneous_subtree_complement.

Incidentally, I realise it is convenient to piggy-back trivial cosmetic
changes along with larger changes, but I'd like to point out that this can
make reviews harder and therefore introduces the risk of missing problems in
the non-trivial parts of the change.  You should consider making all the
trivial changes in another workspace as you go, and committing these before
posting the main diff.

This comment applies to everyone's diffs, not just this one.

> @@ -729,6 +756,9 @@
>  		adjust_unexplored_leaves(yes(Suspect ^ status), Status, 
>  			!SearchSpace)
>  	),
> +	% Remove the suspect's weight from it's ancestors, since its weight is

s/it's/its/

> +	% now zero.

It appears that the weight field does not actually get set to zero, even
though the weight is considered to be zero at this point.  You should document
above that the weight field doesn't contain a meaningful value if the suspect
is valid.

> +	add_weight_to_ancestors(SuspectId, - Suspect ^ weight, !SearchSpace),
>  	%
>  	% If the suspect was erroneous or excluded because of another erronoeus
>  	% suspect, then we should update the complement of the subtree rooted
> @@ -770,32 +800,24 @@
>  		adjust_unexplored_leaves(yes(Suspect ^ status), erroneous, 
>  			!SearchSpace)
>  	;
> -		Suspect ^ children = yes(Children),
> -		%
> -		% If the suspect was correct, inadmissible or pruned then we
> -		% should make all the descendents unknown again.
> -		%
> -		(
> -			excluded_subtree(Suspect ^ status, yes)
> -		->
> -			list.foldl(propagate_status_downwards(unknown, 
> -				[correct, inadmissible]), Children,
> -				!SearchSpace)
> -		;
> -			true
> -		)
> +		Suspect ^ children = yes(_)
>  	),
> -	propagate_status_upwards(in_erroneous_subtree_complement, [erroneous], 
> -		SuspectId, _, !SearchSpace),
> +	propagate_status_upwards(in_erroneous_subtree_complement, 
> +		[erroneous, correct, inadmissible], SuspectId, _,
> +		!SearchSpace),
>  	!:SearchSpace = !.SearchSpace ^ root := yes(SuspectId).

I don't understand these changes to assert_suspect_is_erroneous.  Could you
please document it in the log message, or add comments to the code here, or
preferably both?

> @@ -804,27 +826,44 @@
>  		skipped(N), Store),
>  	!:SearchSpace = !.SearchSpace ^ store := Store.
>  
> -revise_root(!SearchSpace) :-
> +revise_root(Store, !SearchSpace) :-
>  	(
>  		!.SearchSpace ^ root = yes(RootId),
>  		force_propagate_status_downwards(unknown, 
> -			[correct, inadmissible], RootId, Leaves, !SearchSpace),
> -		list.foldl(force_propagate_status_downwards(unknown, [correct,
> -			inadmissible]), Leaves, !SearchSpace),
> -		propagate_status_upwards(unknown, [erroneous], RootId, Lowest, 
> +			[correct, inadmissible], RootId, StopSuspects, 
>  			!SearchSpace),
> -		(
> -			suspect_erroneous(!.SearchSpace, Lowest)
> -		->
> +		list.foldl(force_propagate_status_downwards(unknown, [correct,
> +			inadmissible]), StopSuspects, !SearchSpace),
> +		propagate_status_upwards(unknown, [erroneous, correct,
> +			inadmissible], RootId, Lowest, !SearchSpace),
> +		( suspect_erroneous(!.SearchSpace, Lowest) ->
>  			!:SearchSpace = !.SearchSpace ^ root := yes(Lowest)
>  		;
>  			!:SearchSpace = !.SearchSpace ^ root := no
> -		)
> +		),
> +		%
> +		% Recompute the suspect weights from the bottom up.
> +		%
> +		map.keys(!.SearchSpace ^ store, AllSuspects),
> +		list.filter(suspect_is_leaf(!.SearchSpace), AllSuspects, 
> +			Leaves),
> +		recalc_weights_upto_ancestor(Store, Lowest, Leaves, 
> +			!SearchSpace)
>  	;
>  		!.SearchSpace ^ root = no,
>  		throw(internal_error("revise_root", "no root"))
>  	).

Likewise I don't fully understand the changes to revise_root.  The comment
on the declaration of it probably needs to be updated.  I'll review these
parts of the change after you post a relative diff.

> @@ -979,24 +1018,22 @@
>  			"couldn't find suspect"))
>  	).
>  
> -	% propagate_status_downwards(Status, StopStatusSet, SuspectId, Leaves, 
> -	%	!SearchSpace). 
> +	% propagate_status_downwards(Status, StopStatusSet, SuspectId, 
> +	%	StopSuspects, !SearchSpace). 
>  	% Sets the status of SuspectId and all it's descendents to Status.
>  	% If a descendent (including the suspect) already has a status in
>  	% StopStatusSet then propagate_status_downwards won't update any
>  	% further descendents.  The list of all the children of the lowest
> -	% updated suspects is returned in Leaves.
> +	% updated suspects is returned in StopSuspects.
>  	% 

The change of variable name from Leaves to StopSuspects here and below is okay,
but probably should be mentioned in the log message.

> @@ -1008,12 +1045,14 @@
>  	propagate_status_downwards(Status, StopStatusSet, SuspectId, _, 
>  		!SearchSpace).
>  
> +	% An accumulator version of propagate_status_downwards.
> +	%
>  :- pred propagate_status_downwards(suspect_status::in, 
>  	list(suspect_status)::in, suspect_id::in, 
>  	list(suspect_id)::in, list(suspect_id)::out, 
>  	search_space(T)::in, search_space(T)::out) is det.

The conventional name for such a predicate would be
propagate_status_downwards_2, by the way.

> @@ -1169,9 +1208,157 @@
>  			++ string(SearchSpace) ++ "\n Context is:\n" ++
>  			Context))
>  	;
> +		check_search_space_weights(Store, SearchSpace)
> +	->
> +		% check_search_space_weights will never actually fail, but
> +		% will throw an exception if the weights are inconsistent.

See my comment below.

> +		true
> +	;
>  		true
>  	).
> @@ -1191,11 +1378,59 @@
>  calc_num_unexplored(SearchSpace) = NumUnexplored :-
>  	Suspects = map.values(SearchSpace ^ store),
>  	list.filter(
> -		( pred(suspect(_, _, Status, _, no)::in) is semidet :- 
> +		( pred(suspect(_, _, Status, _, no, _)::in) is semidet :- 
>  			in_buggy_subtree(Status, yes)
>  		), Suspects, Unexplored),
>  	NumUnexplored = list.length(Unexplored).
>  
> +	% Check that the weights in the search space are correct and throw
> +	% an exception if they aren't.
> +	%
> +:- pred check_search_space_weights(S::in, search_space(T)::in) 
> +	is semidet <= mercury_edt(S, T).

This predicate isn't really semidet; presumably you have made it semidet
so that the compiler won't optimise it away.  It would be better to write
a predicate called, say, find_inconsistency_in_weights that fails if there
is no inconsistency and succeeds with some suitable output if there is
one.  Then let the caller construct the exception value and throw it if
required.

> Index: browser/declarative_tree.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_tree.m,v
> retrieving revision 1.11
> diff -u -r1.11 declarative_tree.m
> --- browser/declarative_tree.m	16 Dec 2004 00:12:39 -0000	1.11
> +++ browser/declarative_tree.m	21 Dec 2004 11:30:35 -0000
> @@ -1,5 +1,5 @@
>  %-----------------------------------------------------------------------------%
> -% Copyright (C) 2002-2004 The University of Melbourne.
> +% Copyright (C) 2002-2003 The University of Melbourne.
>  % This file may only be copied under the terms of the GNU Library General
>  % Public License - see the file COPYING.LIB in the Mercury distribution.
>  %-----------------------------------------------------------------------------%

Wrong year, although the check-in script should fix this for you.

> @@ -284,6 +285,94 @@
>  trace_is_implicit_root(wrap(Store), dynamic(Ref)) :-
>  	get_edt_call_node(Store, Ref, CallId),
>  	\+ not_at_depth_limit(Store, CallId).
> +
> +:- pred trace_weight(wrap(S)::in, edt_node(R)::in, int::out, int::out)
> +	is det <= annotated_trace(S, R).
> +
> +trace_weight(Store, NodeId, Weight, ExcessWeight) :- 
> +	node_events(Store, NodeId, 0, Weight, no, 0, 0, ExcessWeight).
> +
> +	% Conservatively guess the number of events in the descendents of the
> +	% call corresponding to the given final event plus the number of
> +	% internal body events for the call.  Also return the number of events
> +	% that could be duplicated in siblings of the node in the EDT if the 
> +	% node is a FAIL event.

Add an extra line break.

> +	% We include all the events between the final event and the last
> +	% REDO before the final event, plus all the events between previous
> +	% EXITs and REDOs and the initial CALL.  For EXIT and EXCP events
> +	% this is an over approximation, but we can't know which events
> +	% will be included in descendent contours when those descendent
> +	% events are in unmaterialized portions of the annotated trace.
> +	%
> +	% node_events(Store, Node, PrevEvents, Events, RecordDups,
> +	%	DupFactor, PrevDupEvents, DupEvents)
> +	% True iff Events is the (conservative approximation of) the number of
> +	% descendent events of Node and DupEvents is the number of events that
> +	% could be duplicated in siblings.  PrevEvents and PrevDupEvents are
> +	% accumlators which should initially be zero.  RecordDups keeps track

s/accumlators/accumulators/

> Index: doc/user_guide.texi
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
> retrieving revision 1.404
> diff -u -r1.404 user_guide.texi
> --- doc/user_guide.texi	20 Dec 2004 01:15:48 -0000	1.404
> +++ doc/user_guide.texi	21 Dec 2004 11:44:21 -0000
> @@ -3256,7 +3257,7 @@
>  @ref{Declarative debugging} for details.
>  @sp 1
>  @table @code
> - at item dd
> + at item dd [-d at var{depth} -s at var{strategy}]

The options are independently optional, so that should be:

@item dd [-d at var{depth}] [-s at var{strategy}]

>  @c @item dd [--assume-all-io-is-tabled]
>  @c The --assume-all-io-is-tabled option is for developers only. Specifying it
>  @c makes an assertion, and if the assertion is incorrect, the resulting
> @@ -3273,6 +3274,18 @@
>  declarative debugger for long running programs since it will not have to rerun
>  the program as much.
>  @sp 1
> +The @samp{-s at var{strategy}} or @samp{--default-search-mode

Either call it a search mode or a search strategy, don't switch between the
two.

> + at var{strategy}} option tells the declarative debugger which 
> +search strategy to use by default.

Either explain precisely what is meant by "default" here, or avoid the
term altogether and just say that the option tells the debugger which search
strategy to use.  (Also, see my comments below.)

Either @samp{top-down} or 
> + at samp{divide-and-query} may be specified.

Give a cross reference to the section on search strategies.  In fact, if you
do this then the brief explanation of the strategies that you give here
should probably be removed.

@samp{top-down} search is more
> +predicable and will ask you about the children of the last atom you

s/predicable/predictable/

> +asserted was erroneous (i.e. gave a `no' answer for), however this may
> +mean that lots of questions will need to be answered before a bug is located.  
> + at samp{divide-and-query} search tries to ask questions that will halve the
> +search space with each answer resulting in quicker localization of the bug,
> +however the questions asked may appear unrelated to each other.  
> + at samp{top-down} is the default when this option is not given.

The use of the term "default" here is what I would normally understand it
to mean.  Hence the use of the term "default" above (and indeed in the code
itself), which has a different sense, is a bit confusing and I would try to
avoid it.

> + at sp 1
>  @item trust @var{module-name}|@var{proc-spec}
>  @kindex trust (mdb command)
>  Tells the declarative debugger to trust the given module, predicate or
> @@ -3883,6 +3897,36 @@
>  If the user aborts the diagnosis,
>  they are returned to the event at which the @samp{dd} command was given.
>  
> + at node Search Strategies
> + at subsection Search Strategies
> +
> +Currently the declarative debugger can employ one of two strategies when
> +searching for a bug.  The initial strategy to use can be specified

"Initial" is better than "default".  However, you should explain why it is
only the initial strategy (that is, point out that the strategy may
automatically change to top-down if the current strategy is no longer
applicable).

> +as an option to the @samp{dd} command.  See 
> + at ref{Declarative debugging mdb commands} for information on how to do this.
> +
> + at subsubsection Top-down Search
> +
> +Using this strategy the declarative debugger will ask about the children
> +of the last atom who's assertion was false.  This makes the search more

s/who's/whose/

> +predictable from the user's point of view as the questions will more
> +or less follow the program execution.  The drawback of top-down search is that
> +it may require a lot of questions to be answered before a bug is found, 
> +especially with deeply recursive program runs.  
> +
> +This search strategy is used by default when no other strategy is specified.
> +
> + at subsubsection Divide and Query Search
> +
> +With this strategy the declarative debugger will attempt to halve the size of
> +the search space with each question.  In most cases this will result in the 

Can you really claim "most" here?  It would depend on the kind of programs
being written.  "Many" would be a safer claim than "most".

> +bug being found after log(N) questions where N is the number of events

That should be O(log(N)).

> +between the event where the @samp{dd} command was given and the corresponding
> + at samp{CALL} event.  This makes the search feasible for deeply recursive runs
> +where top-down search would require an unreasonably large number of questions
> +to be answered.  However, the questions may appear to come from unrelated parts
> +of the program which can make them harder to answer.
> +
>  @node Improving the search
>  @subsection Improving the search
>  
> @@ -3966,13 +4010,13 @@
>  the call that constructed the year part of the date.
>  
>  This feature is also useful when using the procedural debugger.  For example,
> -suppose that you come across a CALL event and you would like to know the source
> -of a particular input to the call.  To find out you could first go to the final
> -event by issuing a @samp{finish} command.  Invoke the declarative debugger with
> -a @samp{dd} command and then mark the input term you are interested in.  The
> -next question should be about the call that bound the term.  Issue a @samp{pd}
> -command at this point to return to the procedural debugger. It will now show
> -the final event of the call that bound the term.
> +suppose that you come across a @samp{CALL} event and you would like to know the
> +source of a particular input to the call.  To find out you could first go to
> +the final event by issuing a @samp{finish} command.  Invoke the declarative
> +debugger with a @samp{dd} command and then mark the input term you are
> +interested in.  The next question should be about the call that bound the term.
> +Issue a @samp{pd} command at this point to return to the procedural debugger.
> +It will now show the final event of the call that bound the term.
>  
>  @subsubsection Trusting predicates, functions and modules
>  

This part of the change is not mentioned in the log message.

> Index: trace/mercury_trace_internal.c
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_internal.c,v
> retrieving revision 1.184
> diff -u -r1.184 mercury_trace_internal.c
> --- trace/mercury_trace_internal.c	16 Dec 2004 00:12:41 -0000	1.184
> +++ trace/mercury_trace_internal.c	16 Dec 2004 00:28:48 -0000
> @@ -5510,10 +5512,19 @@
>  	MR_Event_Info *event_info, MR_Event_Details *event_details,
>  	MR_Code **jumpaddr)
>  {
> +	MR_Decl_Default_Search_Mode	default_search_mode;
> +
>  	MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
>  	MR_edt_depth_step_size = MR_TRACE_DECL_INITIAL_DEPTH;
> +	if (! MR_trace_is_valid_search_mode_string("top_down", 
> +			&default_search_mode))
> +	{
> +		MR_fatal_error("MR_trace_cmd_dd: top_down invalid");
> +	}

That's a roundabout way of doing it.  Why not export a function from
mercury_trace_declarative that returns the default, instead of doing
a string comparison each time?

> +		
>  	if (! MR_trace_options_dd(&MR_trace_decl_assume_all_io_is_tabled,
> -		&MR_edt_depth_step_size, &words, &word_count, "dd", "dd"))
> +		&MR_edt_depth_step_size, &default_search_mode,
> +		&words, &word_count, "dd", "dd"))
>  	{
>  		; /* the usage message has already been printed */
>  	} else if (word_count == 1) {
> @@ -5544,11 +5557,19 @@
>  {
>  	MR_Trace_Mode	trace_mode;
>  	const char	*filename;
> +	MR_Decl_Default_Search_Mode	default_search_mode;
>  
>  	MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
> -	MR_edt_depth_step_size = 3;
> +	MR_edt_depth_step_size = MR_TRACE_DECL_INITIAL_DEPTH;
> +	if (! MR_trace_is_valid_search_mode_string("top_down",
> +			&default_search_mode))
> +	{
> +		MR_fatal_error("MR_trace_cmd_dd_dd: top_down invalid");
> +	}

Ditto.

> +	
>  	if (! MR_trace_options_dd(&MR_trace_decl_assume_all_io_is_tabled,
> -		&MR_edt_depth_step_size, &words, &word_count, "dd", "dd_dd"))
> +		&MR_edt_depth_step_size, &default_search_mode,
> +		&words, &word_count, "dd", "dd_dd"))
>  	{
>  		; /* the usage message has already been printed */
>  	} else if (word_count <= 2) {
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------