[m-rev.] For review: allow declarative debugger to search upward from initial symptom

[Julien Fischer]

On Mon, 29 Nov 2004, Ian MacLarty wrote:

...

> Index: browser/declarative_analyser.m
...
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_analyser.m,v
> retrieving revision 1.16
> diff -u -r1.16 declarative_analyser.m
> --- browser/declarative_analyser.m	19 Nov 2004 11:54:16 -0000	1.16
> +++ browser/declarative_analyser.m	29 Nov 2004 06:36:40 -0000
> @@ -1,5 +1,5 @@
>  %-----------------------------------------------------------------------------%
> -% Copyright (C) 1999-2004 The University of Melbourne.
> +% Copyright (C) 1999-2003 The University of Melbourne.
The year is wrong here.


> @@ -475,9 +521,19 @@
>  	search_response::out, search_mode::out) is det <= mercury_edt(S, T).
>
>  top_down_search(Store, !SearchSpace, Response, NewMode) :-
> -	root_det(!.SearchSpace, RootId),
> +	%
> +	% If there's no root yet (because the oracle hasn't asserted any nodes
> +	% are erroneous yet, then use the topmost suspect as a starting point.
> +	%
There's unmatched parenthesis in that comment.

> @@ -583,27 +652,61 @@
>  		;
>  			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)
> +		(
> +			%
> +			% Check if it's worth continuing tracking the sub-term.
> +			% We want to stop if we enter a portion of the search
> +			% space known not to contain the bug from which we
> +			% can't return (like if we come across an erroneous
> +			% node where the sub-term is an input).
> +			%
Make that last bit "For example, if we come across ..."

> Index: browser/declarative_debugger.m
...

> @@ -543,8 +574,17 @@
>  :- pragma export(diagnoser_require_subtree(in, out, out, out),
>  		"MR_DD_diagnoser_require_subtree").
>
> -diagnoser_require_subtree(require_subtree(Event, SeqNo, CallPreceding), Event,
> -	SeqNo, CallPreceding).
> +diagnoser_require_subtree(require_subtree(Event, SeqNo, CallPreceding),
> +	Event, SeqNo, CallPreceding).
> +
> +:- pred diagnoser_require_supertree(diagnoser_response(trace_node_id),
> +	event_number, sequence_number).
> +:- mode diagnoser_require_supertree(in, out, out) is semidet.
> +
You can use predmode syntax there.

> Index: browser/declarative_edt.m

>
>  suspect_correct_or_inadmissible(SearchSpace, SuspectId) :-
>  	lookup_suspect(SearchSpace, SuspectId, Suspect),
> @@ -523,7 +603,7 @@
>
>  	% Succeeds if we haven't got an answer from the oracle about this
>  	% suspect, and haven't been able to infer anything about this suspect
> -	% from other oracle answers?
> +	% from other oracle answers.
>  	%
>  :- pred suspect_is_questionable(search_space(T)::in, suspect_id::in)
>  	is semidet.
> @@ -593,59 +673,125 @@
>  in_buggy_subtree(in_erroneous_subtree_complement, no).
>  in_buggy_subtree(unknown, yes).
>
> -
> -	% Should the suspect's status be propogated to it's children when the
> -	% children are added to the search space?
> +	% What status should be assigned to children of a node with the given
> +	% status, when the children are being added to the search space?
>  	%
I would reword that comment so that it just describes what the function
does.

> -:- pred propogate_status_to_children(suspect_status::in, bool::out) is det.
> +:- func new_child_status(suspect_status) = suspect_status.
>
> -propogate_status_to_children(ignored, no).
> -propogate_status_to_children(skipped(_), no).
> -propogate_status_to_children(correct, no).
> -propogate_status_to_children(erroneous, no).
> -propogate_status_to_children(inadmissible, no).
> -propogate_status_to_children(pruned, yes).
> -propogate_status_to_children(in_erroneous_subtree_complement, yes).
> -propogate_status_to_children(unknown, no).
> +new_child_status(ignored) = unknown.
> +new_child_status(skipped(_)) = unknown.
> +new_child_status(correct) = pruned.
> +new_child_status(erroneous) = unknown.
> +new_child_status(inadmissible) = pruned.
> +new_child_status(pruned) = pruned.
> +new_child_status(in_erroneous_subtree_complement) =
> +	in_erroneous_subtree_complement.
> +new_child_status(unknown) = unknown.
> +
> +	% What status should be assigned to the parent of a node with the given
> +	% status, when the parent is being added to the search space?
> +	%
Likewise here.

> +:- func new_parent_status(suspect_status) = suspect_status.
> +
> +new_parent_status(ignored) = unknown.
> +new_parent_status(skipped(_)) = unknown.
> +new_parent_status(correct) = unknown.
> +new_parent_status(erroneous) = in_erroneous_subtree_complement.
> +new_parent_status(inadmissible) = unknown.
> +new_parent_status(pruned) = pruned.
> +new_parent_status(in_erroneous_subtree_complement) =
> +	in_erroneous_subtree_complement.
> +new_parent_status(unknown) = unknown.
> +
> +give_up_subterm_tracking(SearchSpace, SuspectId) :-
> +	Status = get_status(SearchSpace, SuspectId),
> +	(Status = erroneous ; Status = in_erroneous_subtree_complement).
>

> +	% A version of trickle_status which doesn't return Leaves.
> +	%
s/Leaves/leaves/.

> +:- pred trickle_status(suspect_status::in, list(suspect_status)::in,
> +	suspect_id::in, search_space(T)::in, search_space(T)::out) is det.
> +
> +trickle_status(Status, StopStatusSet, SuspectId, !SearchSpace) :-
> +	trickle_status(Status, StopStatusSet, SuspectId, _,
> +		!SearchSpace).
>
I'm not sure that using terms like trickle and perculate is very
clear - propagate_upwards and propgate_downwards might be more
straightforward (albeit less colourful).

> -trickle_status(Status, SuspectId, !SearchSpace) :-
> +:- pred trickle_status(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.
> +
> +trickle_status(Status, StopStatusSet, SuspectId, !Leaves, !SearchSpace) :-
>  	lookup_suspect(!.SearchSpace, SuspectId, Suspect),
>  	(
> -		Suspect ^ status \= Status
> +		\+ member(Suspect ^ status, StopStatusSet)
>  	->
>  		map.set(!.SearchSpace ^ store, SuspectId,
>  			Suspect ^ status := Status, Store),
>  		!:SearchSpace = !.SearchSpace ^ store := Store,
>  		(
>  			Suspect ^ children = yes(Children),
> -			list.foldl(trickle_status(Status), Children,
> +			list.foldl2(trickle_status(Status, StopStatusSet),
> +				Children, !Leaves, !SearchSpace)
> +		;
> +			Suspect ^ children = no,
> +			adjust_unexplored_leaves(yes(Suspect ^ status), Status,
>  				!SearchSpace)
> +		),
> +		adjust_unknown_count(yes(Suspect ^ status), Status,
> +			!SearchSpace)
> +	;
> +		!:Leaves = [SuspectId | !.Leaves]
You could also write that as

		list.cons(SuspectId, !Leaves)


> +	% Increments or decremenets the unknown suspect count after a status
s/decremenets/decrements/

> +	% change.  The 1st argument should be the previous status of the
> +	% changed suspect or no if a new suspect is being added and the 2nd
> +	% argument should be the suspect's new status.
> +	%
Use first and second rather than 1st and 2nd.

> +:- pred adjust_unknown_count(maybe(suspect_status)::in, suspect_status::in,
> +	search_space(T)::in, search_space(T)::out) is det.
> +
> +adjust_unknown_count(MaybeOldStatus, NewStatus, !SearchSpace) :-
> +	(
> +		MaybeOldStatus = yes(OldStatus),
> +		questionable(OldStatus, yes),
> +		questionable(NewStatus, no)
> +	->
> +		!:SearchSpace = !.SearchSpace ^ unknown_count :=
> +			!.SearchSpace ^ unknown_count - 1
> +	;
> +		questionable(NewStatus, yes),
> +		(
> +			MaybeOldStatus = no
> +		;
> +			MaybeOldStatus = yes(OldStatus),
> +			questionable(OldStatus, no)
> +		)
> +	->
> +		!:SearchSpace = !.SearchSpace ^ unknown_count :=
> +			!.SearchSpace ^ unknown_count + 1
> +	;
> +		true
> +	).
> +
> +	% Increments or decremenets the unexplored leaves count after a status
> +	% change.  The 1st argument should be the previous status of the
> +	% changed suspect or no if a new suspect is being added and the 2nd
> +	% argument should be the suspect's new status.  The changed suspect
> +	% should be a leaf node (i.e. have its children field set to no).
> +	%
There are some copy and paste errors from above here.

> +	% Add the given EDT node to the top of the search space.  The given
> +	% node should be the parent of the current topmost node in the search
s/the parent/a parent/

> +	% space.
> +	%
> +:- pred insert_new_topmost_node(S::in, T::in,
> +	search_space(T)::in, search_space(T)::out)
> +	is det <= mercury_edt(S, T).
> +
> +insert_new_topmost_node(Store, NewTopMostEDTNode, !SearchSpace) :-
> +	(
> +		edt_children(Store, NewTopMostEDTNode, EDTChildren)
> +	->
> +		topmost_det(!.SearchSpace, OldTopMostId),
> +		lookup_suspect(!.SearchSpace, OldTopMostId, OldTopMost),
> +		(
> +			%
> +			% One of the children of the new top most node will be
s/top most/topmost/
> +			% the old topmost node so filter it out so it isn't
> +			% added twice.
> +			%
> +			find_node_in_list(Store, EDTChildren,
> +				OldTopMost ^ edt_node, Pos),
> +			list.split_list(Pos - 1, EDTChildren, LeftChildren,
> +				[_ | RightChildren])
> +		->
> +			%
> +			% Insert the new topmost node.
> +			%
> +			NewTopMostStatus = new_parent_status(
> +				OldTopMost ^ status),
> +			NewTopMostDepth = OldTopMost ^ depth - 1,
> +			NewTopMost = suspect(no, NewTopMostEDTNode,
> +				NewTopMostStatus, NewTopMostDepth, no),
> +			some [!Counter, !SuspectStore] (
> +				!:Counter = !.SearchSpace ^ suspect_id_counter,
> +				counter.allocate(NewTopMostId, !Counter),
> +				!:SearchSpace =
> +					!.SearchSpace ^ suspect_id_counter :=
> +					!.Counter,
> +				!:SuspectStore = !.SearchSpace ^ store,
> +				map.set(!.SuspectStore, NewTopMostId,
> +					NewTopMost, !:SuspectStore),
> +				!:SearchSpace = !.SearchSpace ^ store :=
> +					!.SuspectStore
> +			),
> +			SiblingStatus = new_child_status(NewTopMostStatus),
> +			add_children(append(LeftChildren, RightChildren),
> +				NewTopMostId, SiblingStatus, !SearchSpace,
> +				ChildrenIds),
> +
> +			%
> +			% Adjust the unexplored leaves count since the new top
> +			% most node was added with no children.
topnost again

> +			%
> +			adjust_unexplored_leaves(no, NewTopMostStatus,
> +				!SearchSpace),
> +
> +			%
> +			% Now add the old topmost node as a child to the new
> +			% topmost node.
> +			%
> +			(
> +				list.split_list(Pos - 1, ChildrenIds,
> +					LeftChildrenIds, RightChildrenIds)
> +			->
> +				append(LeftChildrenIds, [OldTopMostId |
> +					RightChildrenIds],
> +					NewTopMostChildrenIds)
> +			;
> +				throw(internal_error("insert_new_topmost_node",
> +					"invalid position"))
> +			),
> +			some [!SuspectStore] (
> +				!:SuspectStore = !.SearchSpace ^ store,
> +				map.set(!.SuspectStore, NewTopMostId,
> +					NewTopMost ^ children :=
> +					yes(NewTopMostChildrenIds),
> +					!:SuspectStore),
> +				map.set(!.SuspectStore, OldTopMostId,
> +					OldTopMost ^ parent :=
> +						yes(NewTopMostId),
> +					!:SuspectStore),
> +				!:SearchSpace = !.SearchSpace ^ store :=
> +					!.SuspectStore
> +			),
> +			!:SearchSpace = !.SearchSpace ^ topmost :=
> +				yes(NewTopMostId),
> +
> +			adjust_unknown_count(no, NewTopMostStatus,
> +				!SearchSpace)
> +		;
> +			throw(internal_error("insert_new_topmost_node",
> +				"couldn't find event number"))
> +		)
> +
>  	;
> -		map.set(!.SearchSpace ^ store, SuspectId,
> -			Suspect ^ status := unknown, Store),
> -		!:SearchSpace = !.SearchSpace ^ store := Store
> -	),
> +		throw(internal_error("insert_new_topmost_node",
> +			"couldn't get new topmost node's children"))
> +	).
> +
...

> Index: browser/declarative_tree.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_tree.m,v
> retrieving revision 1.10
> diff -u -r1.10 declarative_tree.m
> --- browser/declarative_tree.m	24 Nov 2004 08:46:28 -0000	1.10
> +++ browser/declarative_tree.m	24 Nov 2004 22:57:59 -0000
> @@ -1,5 +1,5 @@
>  %-----------------------------------------------------------------------------%
> -% Copyright (C) 2002-2004 The University of Melbourne.
> +% Copyright (C) 2002-2003 The University of Melbourne.
The year is now wrong.

> Index: trace/mercury_trace_declarative.c
...
> @@ -273,22 +325,102 @@
>  	}
>
>  	/*
> -	** If this event is an interface event then increase or decrease
> -	** the EDT depth appropriately.
> +	** Filter out events for compiler generated procedures.
> +	** XXX Compiler generated unify procedures should be included
> +	** in the annotated trace so that sub-term dependencies can be
> +	** tracked through them.
> +	*/
The comment should mention that uncommenting the code below is necessary
for this to work.

> +	if (MR_PROC_LAYOUT_IS_UCI(entry)) {
> +		/* && !MR_streq("__Unify__",
> +			entry->MR_sle_proc_id.MR_proc_uci.MR_uci_pred_name)) {
> +		*/
> +		return NULL;
> +	}
> +
> +	/*
> +	** Decide if we are inside or outside the subtree or supertree that
> +	** needs to be materialized, ignoring for now any depth limit.
> +	** If we are materializing a supertree then MR_edt_inside will
> +	** be true whenever we are not in the subtree rooted at the call
> +	** corresponding to MR_edt_start_seqno.  If we are materializing a
> +	** subtree then MR_edt_inside will be true whenever we are in the
> +	** subtree rooted at the call corresponding to MR_edt_start_segno.
> +	*/
> +	if (MR_edt_building_supertree) {
> +		if (!MR_edt_inside) {
> +			if (event_info->MR_call_seqno == MR_edt_start_seqno &&
> +				MR_port_is_final(event_info->MR_trace_port))
> +			{
> +				/*
> +				** We are exiting the subtree rooted at
> +				** MR_edt_start_seqno.
> +				*/
> +				MR_edt_inside = MR_TRUE;
> +			} else {
> +				/*
> +				** We are in an existing explicit subtree.
> +				*/
> +				MR_decl_checkpoint_filter(event_info);
> +				return NULL;
> +			}
> +		} else {
> +			if (event_info->MR_call_seqno == MR_edt_start_seqno) {
> +				/*
> +				** The port must be either CALL or REDO;
> +				** we are leaving the supertree and entering
> +				** the existing explicit subtree.
> +				** We must still however add this node to the
> +				** genertaed EDT, so we don't return here.
> +				*/
s/genertaed/generated/

> +				MR_edt_inside = MR_FALSE;
> +			}
> +		}
> +	} else {
> +		if (MR_edt_inside) {
> +			if (event_info->MR_call_seqno == MR_edt_start_seqno &&
> +				MR_port_is_final(event_info->MR_trace_port))
> +			{
> +				/*
> +				** We are leaving the topmost call.
> +				*/
> +				MR_edt_inside = MR_FALSE;
> +			}
> +		} else {
> +			if (event_info->MR_call_seqno == MR_edt_start_seqno) {
> +				/*
> +				** The port must be either CALL or REDO;
> +				** we are (re)entering the topmost call.
> +				*/
> +				MR_edt_inside = MR_TRUE;
> +			} else {
> +				/*
> +				** Ignore this event---it is outside the
> +				** topmost call.
> +				*/
> +				MR_decl_checkpoint_filter(event_info);
> +				return NULL;
> +			}
> +		}
> +	}
> +
> +	/*
> +	** If the current event is an interface event then increase or decrease
> +	** the EDT depth appropriately.  Note that we must be inside the
> +	** portion of the trace being materialized (ignoring the depth limit)
> +	** when we reach this point.
>  	*/
>  	if (event_info->MR_trace_port == MR_PORT_CALL
>  			|| event_info->MR_trace_port == MR_PORT_REDO) {
>  		MR_edt_depth++;
> +		depth_check_adjustment = 0;
>  	}
> -	if (event_info->MR_trace_port == MR_PORT_EXIT
> -			|| event_info->MR_trace_port == MR_PORT_FAIL
> -			|| event_info->MR_trace_port == MR_PORT_EXCEPTION) {
> +	if (MR_port_is_final(event_info->MR_trace_port)) {
>  		/*
> -		** The depth of the EXIT, FAIL or EXCP event is actually
> -		** MR_edt_depth (not MR_edt_depth-1), however we need to
> -		** adjust the depth here for future events.  This
> -		** inconsistency is neutralised by adjusting the depth
> -		** limit check by setting depth_check_adjustment.
> +		** The depth of the EXIT, FAIL or EXCP event is
> +		** actually MR_edt_depth (not MR_edt_depth-1), however
> +		** we need to adjust the depth here for future events.
> +		** This inconsistency is neutralised by adjusting the
> +		** depth limit check by setting depth_check_adjustment.
>  		*/
>  		MR_edt_depth--;
>  		depth_check_adjustment = 1;
...

> @@ -1237,26 +1348,39 @@
>  static	MR_Code *
>  MR_trace_restart_decl_debug(
>  	MR_Trace_Node call_preceding, MR_Unsigned event, MR_Unsigned seqno,
> -	MR_Trace_Cmd_Info *cmd, MR_Event_Info *event_info,
> -	MR_Event_Details *event_details)
> +	MR_bool create_supertree, MR_Trace_Cmd_Info *cmd, MR_Event_Info
> +	*event_info, MR_Event_Details *event_details)
>  {
> -	MR_Unsigned		depth_limit;
> +	MR_Unsigned		edt_depth_limit;
>  	const char		*message;
>  	MR_Code			*jumpaddr;
>
> -	depth_limit = MR_edt_max_depth + MR_edt_depth_step_size;
> +	MR_edt_return_node = (MR_Trace_Node) NULL;
>
>  	/*
> -	** Set this to the preceding node, so the new subtree's parent is
> +	** Set this to the preceding node, so the new explicit tree's parent is
>  	** resolved correcly.
s/correcly /correctly/

>  	*/
>  	MR_trace_current_node = call_preceding;
>
> -	MR_edt_depth = MR_edt_initial_depth;
> +	/*
> +	** If we're going to build a supertree above the current root, then
> +	** adjust the depth of the topmost node.
> +	*/
> +	if (create_supertree) {
> +		if (MR_edt_depth_step_size < MR_edt_topmost_call_depth) {
> +			MR_edt_topmost_call_depth -= MR_edt_depth_step_size;
> +		} else {
> +			MR_edt_topmost_call_depth = 1;
> +		}
> +	}
> +	edt_depth_limit = MR_edt_depth_step_size + 1;
> +
> +	MR_edt_depth = 0;

> Index: trace/mercury_trace_internal.c
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_internal.c,v
> retrieving revision 1.180
> diff -u -r1.180 mercury_trace_internal.c
> --- trace/mercury_trace_internal.c	16 Nov 2004 00:45:14 -0000	1.180
> +++ trace/mercury_trace_internal.c	19 Nov 2004 11:56:02 -0000
> @@ -532,8 +532,8 @@
>  			MR_bool *split, MR_bool *close_window, char ***words,
>  			int *word_count, const char *cat, const char*item);
>  static	MR_bool	MR_trace_options_dd(MR_bool *assume_all_io_is_tabled,
> -			char ***words, int *word_count,
> -			const char *cat, const char *item);
> +			MR_Integer *depth_step_size, char ***words,
> +			int *word_count, const char *cat, const char *item);
>  static	MR_bool	MR_trace_options_type_ctor(MR_bool *print_rep,
>  			MR_bool *print_functors, char ***words,
>  			int *word_count, const char *cat, const char *item);
> @@ -5335,8 +5335,9 @@
>  	MR_Code **jumpaddr)
>  {
>  	MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
> +	MR_edt_depth_step_size = 3;
Why 3?

>  	if (! MR_trace_options_dd(&MR_trace_decl_assume_all_io_is_tabled,
> -		&words, &word_count, "dd", "dd"))
> +		&MR_edt_depth_step_size, &words, &word_count, "dd", "dd"))
>  	{
>  		; /* the usage message has already been printed */
>  	} else if (word_count == 1) {
> @@ -5369,8 +5370,9 @@
>  	const char	*filename;
>
>  	MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
> +	MR_edt_depth_step_size = 3;
and here?  I think you should use a symbolic constant.


That's all.

Cheers,
Julien.





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