[m-rev.] For review: changes to declarative debugger (Part 1)

[Ian MacLarty]

On Thu, Oct 28, 2004 at 03:49:19PM +1000, Zoltan Somogyi wrote:
> On 29-Sep-2004, Ian MacLarty <maclarty at cs.mu.OZ.AU> wrote:
> > For review by Zoltan.
> 
> Here is my review of the initial portion. More to come later.
> 
> Zoltan.
> 
> > Lot's of stuff in declarative_analyser.m has been redesigned to facilitate 
> > future improvements, such as probabalistic debugging.
> 
> Lot's -> Lots
> 
Fixed
> > tests/debugger/declarative/trust.inp2
> > 	Tests for new debugger features and changes to some old tests.
> 
> What are those changes?
> 
Here is the new log.  Note that I've removed the changes to the revise test
as they turned out to be unnecessary.

tests/debugger/declarative/Mmakefile
	Added new tests.  Also made it possible to specify 3 different inputs:
	one for non-debugging grades, one for debug grades and one for
	decldebug grades.

tests/debugger/declarative/binary_search.exp
tests/debugger/declarative/binary_search.exp2
tests/debugger/declarative/binary_search.inp
tests/debugger/declarative/binary_search.inp2
tests/debugger/declarative/binary_search.m
tests/debugger/declarative/binary_search_1.m
	Test binary search.

tests/debugger/declarative/builtin_call_rep.exp
tests/debugger/declarative/builtin_call_rep.inp
tests/debugger/declarative/builtin_call_rep.m
	Test that builtin_call_rep appears in the program representation
	for builtin calls.

tests/debugger/declarative/catch.exp3
tests/debugger/declarative/catch.inp3
	Added new input and expected output for decldebug grade.  Since the
	library is now compiled with deep tracing in this grade event numbers
	and call depths are different and some questions in the DD session
	about calls in the exception module need to be answered before the
	desired error message is shown.  Removed contexts from output.

tests/debugger/declarative/closure_dependency.exp
tests/debugger/declarative/closure_dependency.exp2
tests/debugger/declarative/closure_dependency.inp
tests/debugger/declarative/closure_dependency.inp2
tests/debugger/declarative/closure_dependency.m
	Test dependency tracking through higher order calls.

tests/debugger/declarative/confirm_abort.exp
tests/debugger/declarative/confirm_abort.inp
	If the dd command is typed then the root node is now always asked as
	the first question even if the oracle knows the answer (except where
	the predicate is trusted).  Updated the test to reflect this change.

tests/debugger/declarative/dependency.exp
tests/debugger/declarative/dependency2.exp
	Arguments are now counted from the back (a change to get dependency
	tracking to work with higher order calls), so the debug messages 
	printed in this test needed to be changed.

tests/debugger/declarative/explicit_subtree.exp
tests/debugger/declarative/explicit_subtree.exp2
tests/debugger/declarative/explicit_subtree.inp
tests/debugger/declarative/explicit_subtree.m
	Test for a bug fixed with this diff.  The bug occured when the subtree
	for an implicit node was generated and then the explicit subtree for
	another implicit node to the left of the generated subtree was 
	requested.  When building the new subtree execution proceeded from 
	where execution stopped when the previous subtree was generated, so 
	execution never passed through nodes to the left of the 
	previous subtree and the requested subtree wasn't built.

tests/debugger/declarative/family.exp
tests/debugger/declarative/family.inp
	Some changes to event numbers to do with changes in the way explicit
	subtrees are generated (see comment for
	tests/debugger/declarative/explicit_subtree above).  Also some changes
	to do with the fact that the analyser now only asks the oracle one
	question at a time.

tests/debugger/declarative/find_origin.exp
tests/debugger/declarative/find_origin.exp2
tests/debugger/declarative/find_origin.exp3
tests/debugger/declarative/find_origin.inp
tests/debugger/declarative/find_origin.inp2
tests/debugger/declarative/find_origin.inp3
tests/debugger/declarative/find_origin.m
	Test sub-term dependency tracking.

tests/debugger/declarative/ho5.exp3
	Changes to do with the fact that the standard library is now 
	compiled with deep tracing in the decldebug grade.

tests/debugger/declarative/ignore.exp
tests/debugger/declarative/ignore.exp2
tests/debugger/declarative/ignore.exp3
tests/debugger/declarative/ignore.inp
tests/debugger/declarative/ignore.inp2
tests/debugger/declarative/ignore.inp3
tests/debugger/declarative/ignore.m
tests/debugger/declarative/ignore_1.m
	Test `ignore' oracle response.

tests/debugger/declarative/inadmissible.exp
tests/debugger/declarative/inadmissible.exp2
tests/debugger/declarative/inadmissible.inp
tests/debugger/declarative/inadmissible.inp2
tests/debugger/declarative/inadmissible.m
	Test inadmissibility.

tests/debugger/declarative/input_term_dep.exp
tests/debugger/declarative/input_term_dep.inp
	Some of the bugs found are now inadmissible call bugs, since inputs
	were marked as incorrect.  Also made changes to do with the fact that 
	incorrect sub-terms are now followed to where they're bound.

tests/debugger/declarative/lpe_example.exp3
	Added new expected output when in decldebug grade.  Event numbers and
	call depths are different now because of deep tracing in the standard
	library.

tests/debugger/declarative/mismatch_on_call.exp
tests/debugger/declarative/mismatch_on_call.exp2
tests/debugger/declarative/mismatch_on_call.inp
tests/debugger/declarative/mismatch_on_call.m
	This test used to cause an "mismatch on call" exception to be thrown 
	by the dependency tracking routine.

tests/debugger/declarative/skip.exp
tests/debugger/declarative/skip.exp2
tests/debugger/declarative/skip.inp
tests/debugger/declarative/skip.m
	Test `skip' oracle response.

tests/debugger/declarative/solutions.exp3
tests/debugger/declarative/solutions.inp3
	Added new input and expected output for decldebug grade.
	Some standard modules need to be trusted since they are now deep traced
	in this grade.

tests/debugger/declarative/special_term_dep.exp
	A bug is now reported as an inadmissible call.

tests/debugger/declarative/throw.exp3
	Because the standard library in decldebug grade is now deep traced
	by default event numbers are different, parent contexts are printed
	and "reached label with no stack layout info" warnings are not 
	encountered.

tests/debugger/declarative/trust.exp2
tests/debugger/declarative/trust.inp2
	Added new input and expected output to handle questions asked about
	predicates in the string module (which is now deep traced in decldebug
	grade).

> > trace/mercury_trace_declarative.c
> > 	Made the depth step size used when deciding which events to put in 
> > 	the annotated trace a variable so that it can be dynamically adjusted
> > 	in the future.
> > 	The EDT depth is now calculated instead of using the call depth (which
> > 	is not always consistent with the EDT depth).
> 
> I presume you mean "instead of the call depth"?
> 
No, the call depth (event_info->MR_call_depth) wasn't calculated here, but
was used as the depth of the EDT.  The EDT depth is now calculated
independently.  I haven't changed the code that calculates
event_info->MR_call_depth.

I changed the log to:

	The EDT depth is now calculated independently instead of using
	event_info->MR_call_depth (which is not always consistent with
	the EDT depth).

Is that clearer?

> > 	Made changes so that all the interface events for the sub-calls inside
> > 	a call are included in the annotated trace, so that contours are built
> > 	correctly.
> 
> This breaks the depth limit, so I suspect you don't mean that in all cases.
> 
It does break the depth limit, but only ever by 1 and is 
necessary to build correct contours.  What do you mean "in all cases"?

> > :- pred revise_analysis(S::in, analyser_response(T)::out, analyser_state(T)::in,
> > 	analyser_state(T)::out) is det <= mercury_edt(S, T).
> 
> Break up that line.
> 
> > 			% Look for the first unknown suspect in a breadth-first 
> > 			% fashion, starting at the root.  If no unknown
> > 			% suspects are found then choose a skipped suspect
> > 			% to requery.
> > 	--->	breadth_first
> 
> Breadth first is a bad name. Neither breadth_first nor depth_first mean
> much here, because if a node is valid, its children aren't searched.
> I think you mean simply top-down left-to-right.
> 
I agree and have changed breadth_first to top_down throughout.

> > 			%
> > 			% Follow the subterm all the way to where it's bound or
> > 			% until it can't be followed any further (for example
> > 			% when there is a call to a module with no tracing),
> > 			% and ask a question about the nearest unknown suspect
> > 			% on the subterm dependency chain.  Then proceed to do
> > 			% a binary search between this node and the root of the
> > 			% search space (The binary search will only come into
> > 			% effect if the oracle asserts the suspect is correct
> > 			% or inadmissible).
> 
> "The" -> "the"
> 
Fixed.
> > 			% explicit subtree to be generated.  The last argument
> > 			% is the last suspect on the dependency chain whos
> > 			% status was unknown (initially this is no).
> 
> "whos" -> "whose"
Fixed.
> 
> Was unknown when? Last in what direction? More documentation needed here.
>

			% explicit subtree to be generated.  The last argument
			% is the last suspect on the dependency chain whose
			% status was unknown.  Initially this is no, but as the
			% sub-term is tracked to where is was initially bound
			% (which could be above or below the node where it was
			% marked incorrect), the most recent node through which
			% the subterm was tracked that has a status of
			% `unknown' is stored in this field.  This is then used
			% as the next question if the node that bound the
			% subterm is trusted or in an excluded part of the
			% search tree.
			%
> > 			%
> > 			% Perform a binary search on the array of suspects.
> > 			% The range field gives the subrange of the array to
> > 			% search.  last_tested is the index into the array of
> > 			% the last suspect about which a question was asked.   
> > 			%
> 
> Where do the array elements come from, and what invariants hold on them?
> The range endpoints: are they inclusive or exclusive?
> 
			%
			% Perform a binary search on a path in the search space
			% between a suspect and an ancestor of the suspect.
			% The path is represented as an array (the 1st
			% argument) with the deeper suspect at the end of the
			% array and its ancestor at the beginning.
			% The range field gives the inclusive subrange of the
			% array to search.  last_tested is the index into the
			% array of the last suspect about which a question was
			% asked.   
			%
> > 	;	binary(
> > 			suspects	:: array(suspect_id),
> > 			range		:: pair(int, int),
> > 			last_testsed	:: int
> > 		).
> 
> last_testsed -> last_tested
> 
Fixed.
> > analyser_state_init(IoActionMap, Analyser) :-
> > 	empty_search_space(EmptySearchSpace),
> > 	Analyser = analyser(EmptySearchSpace, [], no, breadth_first, no, 
> > 		IoActionMap, no).
> 
> Make empty_search_space a function.
> 
Done.
> > analyser_state_replace_io_map(IoActionMap, Analyser0, Analyser) :-
> > 	Analyser = Analyser0 ^ io_action_map := IoActionMap.
> 
> Use state variable notation.
> 
Done.
> 
> Since start_analysis with MaybeRequireExplicit = yes just continues an
> existing analysis, you should rename the predicate.
> 
Do you think start_or_resume_analysis is a good name?

> > revise_analysis(Store, Response, !Analyser) :-
> > 	%
> > 	% The head of the previous_roots field in the analyser is just the
> 
> Fields don't have heads, only lists do.
> 
	% The head of previous_roots in the analyser is just the

> > 	% current root of the search space, so we make the second element in
> > 	% previous_roots the new erroneous root, make everything below it
> > 	% unknown and re-query the current root.  If there's only one previous
> 
> Is "current root" the same as "new erroneous root"?
> 
No,
	% current root of the search space, so we make the second element in
	% previous_roots the new root, make everything below it
	% unknown and re-query the current root.  If there's only one previous

> > search(Store, !SearchSpace, breadth_first, NewMode, Response) :-
> > 	breadth_first_search(Store, !SearchSpace, Response, NewMode).
> 
> breadth_first_search should be renamed, for the reason given above.
> 
Done.

> > breadth_first_search(Store, !SearchSpace, Response, NewMode) :-
> > 	root_det(!.SearchSpace, RootId),
> > 	(
> > 		first_unknown_descendent_breadth(Store, RootId, 
> > 			!.SearchSpace, SearchSpace1, MaybeDescendent)
> > 	->
> > 		SearchSpace1 = !:SearchSpace,
> > 		(
> > 			MaybeDescendent = yes(Unknown),
> > 			Response = question(Unknown),
> > 			NewMode = breadth_first
> > 		;
> > 			MaybeDescendent = no,
> > 			(
> > 				choose_skipped_suspect(!.SearchSpace,
> > 					LeastSkipped)
> > 			->
> > 				Response = question(LeastSkipped),
> > 				NewMode = breadth_first
> 
> Why *Least*Skipped?
> 
Oh that was a name I used when choose_skipped_suspect was named
least_skipped_suspect.  I originally counted how many times each suspect was
skipped and then used the least skipped one if only skipped suspects 
remained, however now choose_skipped_suspect chooses the suspect that was
skipped the longest time ago.  I've now changed the variable name to 
just SkippedSuspect.

> > 				throw(internal_error("breadth_first_search",
> > 					"no unknown or skipped suspects"))
> > 			)
> > 		)
> > 	;
> > 		%
> > 		% An explicit subtree is required, so pick an implicit root
> > 		% to make explicit.
> > 		% 
> > 		(
> > 			pick_implicit_root(Store, !.SearchSpace, ImplicitRoot)
> > 		->
> > 			Response = require_explicit(ImplicitRoot),
> > 			NewMode = breadth_first
> 
> Could this decide to materialize a node that is not a child of RootId? If yes,
> why? If not, document why it can't.
> 

		% An explicit subtree is required, so pick an implicit root
		% to make explicit.  pick_implicit_root/3 will choose an
		% implicit root that is a descendent of the root id of the 
		% search space.  There is no point in making an implicit root
		% that is not a descendent of the root id explicit, since
		% all suspects above the root id have been excluded from the
		% bug search.  pick_implicit_root will also not choose an
		% implicit root that is a descendent of a correct or
		% inadmissible node, for the same reason.

> > 			throw(internal_error("breadth_first_search",
> > 				"first_unknown_descendent_breadth required "++
> > 				"an explicit subtree, but pick_implicit_roo"++
> > 				"t couldn't find an implicit root"))
> 
> The error message is contradictory.
> 
The two predicates are contradicting each other, so that's why I throw an
exception, as this shouldn't happen.

> > follow_subterm_end_search(Store, !SearchSpace, LastUnknown, SuspectId, ArgPos, 
> > 		TermPath, NewMode, SearchResponse) :-
> > 	find_subterm_origin(Store, SuspectId, ArgPos, TermPath, !SearchSpace,
> > 		FindOriginResponse),
> > 	root_det(!.SearchSpace, RootId),
> > 	(
> > 		FindOriginResponse = primitive_op(_, _),
> > 		(
> > 			LastUnknown = yes(Unknown),
> > 			SearchResponse = question(Unknown),
> > 			setup_binary_search(!.SearchSpace, RootId, Unknown,
> > 				NewMode)
> > 		;
> > 			LastUnknown = no,
> > 			breadth_first_search(Store, !SearchSpace, 
> > 				SearchResponse, NewMode)
> > 		)
> > 	;
> > 		FindOriginResponse = not_found,
> > 		(
> > 			LastUnknown = yes(Unknown),
> > 			SearchResponse = question(Unknown),
> > 			setup_binary_search(!.SearchSpace, RootId, Unknown,
> > 				NewMode)
> > 		;
> > 			LastUnknown = no,
> > 			breadth_first_search(Store, !SearchSpace,
> > 				SearchResponse, NewMode)
> > 		)
> 
> The code for primitive_op and not_found seem identical. Is this intentional,
> and if so, why?
> 
For now the behaviour is the same: if the sub-term is bound by a primitive
operation in the node, then the node is at the end of the dependency chain; if
there is no more tracing information then the node is also at the end of the
dependency chain.

In future the filename and line number of the primitive operation could be
printed out if the node in which the primitive operation occured turned out
to be a bug.
> > 		(
> > 			suspect_unknown(!.SearchSpace, OriginId)
> > 		->
> > 			follow_subterm_end_search(Store, !SearchSpace, 
> > 				yes(OriginId), OriginId, OriginArgPos, 
> > 				OriginTermPath, NewMode, SearchResponse)
> > 		;
> > 			follow_subterm_end_search(Store, !SearchSpace, 
> > 				LastUnknown, OriginId, OriginArgPos,
> > 				OriginTermPath, NewMode, SearchResponse)
> > 		)
> > 	).
> 
> Factor out the common code of the call here. Document why the recursive call
> won't lead to an infinite loop.
I also added a comment to the require_explicit case:
		FindOriginResponse = require_explicit,
		SearchResponse = require_explicit(SuspectId),
		%
		% Record the current position of the search so 
		% we can continue where we left off once the explicit
		% subtree has been generated.
		%
		NewMode = follow_subterm_end(SuspectId, ArgPos, TermPath,
			LastUnknown)
	;
		FindOriginResponse = origin(OriginId, OriginArgPos, 
			OriginTermPath),
		(
			suspect_unknown(!.SearchSpace, OriginId)
		->
			NewLastUnknown = yes(OriginId)
		;
			NewLastUnknown = LastUnknown
		),
		%
		% This recursive call will not lead to an infinite loop because
		% eventually either the sub-term will be bound (and
		% find_subterm_origin will respond with primitive_op/2) or
		% there will be insufficient tracing information to continue
		% (and find_subterm_origin will respond with not_found).
		%
		follow_subterm_end_search(Store, !SearchSpace, 
			NewLastUnknown, OriginId, OriginArgPos,
			OriginTermPath, NewMode, SearchResponse)
	).

Thanks for the comments,

Ian.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------