[m-rev.] for review: improvements to subterm dependency tracking

[Zoltan Somogyi]

On 30-Oct-2005, Ian MacLarty <maclarty at cs.mu.OZ.AU> wrote:
> If the user tracks a subterm, do not interpret this as an assertion that the
> atom is erroneous or inadmissible.  Experience has should that this behaviour

... has SHOWN

> is not all that useful and requires much more thought from the user before they
> track a subterm, because the user must be sure the atom is in fact erroneous or
> inadmissible before tracking the subterm.  The user may just be suspicious of
> the subterm and may not be willing or able to assert that the atom is
> erroneous or inadmissible.

This is fine as the default, However, there should me a mechanism that tracks
the subterm AND asserts the incorrectness of the atom.

> doc/user_guide.texi:
> 	Change the documentation accordingly.
> 
> browser/browse.m:
> browser/browser_info.m:
> browser/parse.m:
> browser/declarative_user.m:
> 	Change the `mark' command to `track' and allow an `--accurate' or `-a'
> 	argument.
> 	Pass information about tracked subterms to the declarative debugger.

What's the rationale for the change in name?

We could use "mark" to mean "track, and assert the atom is not valid".

> browser/declarative_analyser.m:
> browser/declarative_debugger.m:
> browser/declarative_edt.m:
> browser/declarative_oracle.m:
> 	Implement the new tracking algorithm.
> 
> browser/term_rep.m:
> 	Add a predicate to dereference a subterm in another term.
> 
> mdbcomp/rtti_access.m:
> 	Add a predicate to find a candidate input argument on which to
> 	apply the new heuristic.
> 
> runtime/Mmakefile:
> runtime/mercury_layout_util.h:
> runtime/mercury_stack_layout.h:
> trace/mercury_trace_vars.c:
> trace/mercury_trace_vars.h:
> 	Move the function for finding the name of a variable to the runtime,
> 	so that it can be called from the declarative debugger.
> 
> tests/debugger/declarative/Mmakefile:
> tests/debugger/declarative/nodescend_tracking.exp:
> tests/debugger/declarative/nodescend_tracking.inp:
> tests/debugger/declarative/nodescend_tracking.m:
> 	Test the new heuristic.
> 
> tests/debugger/declarative/*
> 	Update expected output to expect `track' instead of `mark' and
> 	adjust tests that relied on `mark' implying that the atom was
> 	erroneous or inadmissible.

> - at subsubsection Marking incorrect subterms
> + at subsubsection Tracking incorrect subterms

You probably want to change this to "Tracking suspicious subterms".

> +:- type maybe_track_subterm_browser
> +	--->	no_track
> +	;	track_accurate(list(dir))
> +	;	track_fast(list(dir)).
> +

I suspect any future changes would be easier if this were

:- type maybe_track_subterm_browser
	--->	no_track
	;	track(how_track_subterm, list(dir))

You could even make it

:- type maybe_track_subterm_browser
	--->	no_track
	;	track(how_track_subterm, should_assert_invalid, list(dir))

> -	;	mark(path)
> -	;	mark
> +	;	track_accurate(path)
> +	;	track_fast(path)
> +	;	track_accurate
> +	;	track_fast

This would also be simpler as

	;	track(track_alg, maybe(path))

> @@ -187,6 +189,7 @@
>  	;	(<)
>  	;	num(int)
>  	;	name(string)
> +	;	arg(string)
>  	;	unknown(char).
> 
>  parse__read_command(Prompt, Command, !IO) :-
> @@ -248,6 +251,8 @@
>  	; C = ('<') ->
>  		Toks = [(<) | Toks2],
>  		lexer_word_chars(Cs, Toks2)
> +	; C = ('-'), Cs = [H | T] ->
> +		lexer_arg([H | T], Toks)
>  	; char__is_digit(C) ->
>  		dig_to_int(C, N),
>  		lexer_num(N, Cs, Toks)
> @@ -281,6 +286,16 @@
>  	char__to_int(C, CN),
>  	N = CN - Zero.
> 
> +:- pred lexer_arg(list(char)::in(non_empty_list), list(token)::out) is det.
> +
> +lexer_arg([Head | Tail], Toks) :-
> +	( Head = ('-') ->
> +		string__from_char_list(Tail, ArgName)
> +	;
> +		string__from_char_list([Head | Tail], ArgName)
> +	),
> +	Toks = [arg(ArgName)].
> +

Am I correct in believing that these changes are for debugging your diff?
You should probably keep them, but document them in the manual, though you
may wish the documentation to be commented out, so as to be visible only
to developers.

>  	Response = user_answer(Question, skip(Node)).
> 
> -handle_command(browse_arg(MaybeArgNum), UserQuestion, Response,
> -		!User, !IO) :-
> +handle_command(browse_arg(MaybeArgNum), UserQuestion, Response, !User, !IO) :-
>  	Question = get_decl_question(UserQuestion),
>  	edt_node_trace_atoms(Question, InitAtom, FinalAtom),
>  	(
>  		MaybeArgNum = yes(ArgNum),
> -		browse_atom_argument(InitAtom, FinalAtom, ArgNum, MaybeMark,
> +		browse_atom_argument(InitAtom, FinalAtom, ArgNum, MaybeTrack,
>  			!User, !IO),
>  		(
> -			MaybeMark = no,
> +			MaybeTrack = no_track,
>  			query_user(UserQuestion, Response,
>  				!User, !IO)
>  		;
> -			MaybeMark = yes(Mark),
> +			MaybeTrack = track_fast(TermPath),
> +			ArgPos = arg_num_to_arg_pos(ArgNum),
> +			Node = get_decl_question_node(Question),
> +			Answer = suspicious_subterm(Node, ArgPos, TermPath,
> +				track_fast),
> +			Response = user_answer(Question, Answer)
> +		;
> +			MaybeTrack = track_accurate(TermPath),
>  			ArgPos = arg_num_to_arg_pos(ArgNum),
>  			Node = get_decl_question_node(Question),
> -			Answer = suspicious_subterm(Node, ArgPos, Mark),
> +			Answer = suspicious_subterm(Node, ArgPos, TermPath,
> +				track_accurate),
>  			Response = user_answer(Question, Answer)

This duplicate code would be factored out with the representation I recommend
above.

>  		MaybeArgNum = no,
> -		browse_atom(InitAtom, FinalAtom, MaybeMark, !User, !IO),
> +		browse_atom(InitAtom, FinalAtom, MaybeTrack, !User, !IO),
>  		(
> -			MaybeMark = no,
> +			MaybeTrack = no_track,
>  			query_user(UserQuestion, Response,
>  				!User, !IO)
>  		;
> -			%
> -			% If the user marks the predicate or function,
> -			% we make the atom erroneous.
> -			%
> -			MaybeMark = yes([]),
> +			MaybeTrack = track_fast([ArgNum | TermPath]),
> +			ArgPos = arg_num_to_arg_pos(ArgNum),
>  			Node = get_decl_question_node(Question),
> -			Answer = truth_value(Node, erroneous),
> +			Answer = suspicious_subterm(Node, ArgPos, TermPath,
> +				track_fast),
>  			Response = user_answer(Question, Answer)
>  		;
> -			MaybeMark = yes([ArgNum | Mark]),
> +			MaybeTrack = track_accurate([ArgNum | TermPath]),
>  			ArgPos = arg_num_to_arg_pos(ArgNum),
>  			Node = get_decl_question_node(Question),
> -			Answer = suspicious_subterm(Node, ArgPos, Mark),
> +			Answer = suspicious_subterm(Node, ArgPos, TermPath,
> +				track_accurate),
>  			Response = user_answer(Question, Answer)

Same here.

> +:- type maybe_track_subterm_user
> +	--->	no_track
> +	;	track_accurate(term_path)
> +	;	track_fast(term_path).

I think this type and maybe_track_subterm_browser could both be instances
of the same type

:- type maybe_track_subterm(T)
	--->	no_track
	;	track(track_alg, should_assert_invalid, T)

with T=list(dir) in one case and T=term_path in the other case.

>  	edt_dependency(Store, Node, ArgPos, TermPath, _, DebugOrigin),
>  	!:Analyser = !.Analyser ^ debug_origin := yes(DebugOrigin),
> 
> -	edt_subterm_mode(Store, Node, ArgPos, TermPath, Mode),
> -	(
> -		Mode = subterm_in,
> -		assert_suspect_is_inadmissible(SuspectId,
> -			!.Analyser ^ search_space, SearchSpace)
> -	;
> -		Mode = subterm_out,
> -		assert_suspect_is_erroneous(SuspectId,
> -			!.Analyser ^ search_space, SearchSpace)
> -	),
> -	!:Analyser = !.Analyser ^ search_space := SearchSpace,
>  	!:Analyser = !.Analyser ^ search_mode := follow_subterm_end(SuspectId,
> -		ArgPos, TermPath, no).
> +		ArgPos, TermPath, no, HowTrack).

The code you deleted here should be conditionally executed if
"should_assert_invalid" indicates it should.

> +	% subtrees unnecessarily.  If the subterm is being tracked through an
> +	% output argument, and there is an input argument with the same
> +	% name as the output argumnet, except for a numerical suffix, then

s/argumnet/argument/

> +	% find_subterm_origin will check if the subterm appears in the same
> +	% position in the input argument.  If it does then it will continue
> +	% tracking the subterm in the input argument, thus bypassing the
> +	% subtree rooted at the call.  Since dereferencing a subterm in a
> +	% large structure can be expensive, find_subterm_origin will only
> +	% try to bypass calls to procedures it has not tried to bypass
> +	% before.  The HowTrack argument specfies whether to use the bypassing
> +	% find_subterm_origin can use heuristics to avoid materialising

s/specfies/specifies/

> +	% heuristics and !TriedShortcutProcs keeps track of which procedures'

To avoid materialising what?

> +deref_path(Term, Path, SubTerm):-
> +	(
> +		Path = [],
> +		SubTerm = Term
> +	;
> +		Path = [Head | Tail],
> +		%
> +		% There is only one representation of a subterm, given
> +		% the representation of the containing term and a term path.
> +		%
> +		promise_equivalent_solutions [NextSubTerm] (
> +			rep_to_univ(Term, Univ),
> +			% Argument indexes in the term path start from one, but
> +			% the argument function wants argument indexes to
> +			% start from zero.
> +			SubUniv = argument(univ_value(Univ), Head - 1),
> +			univ_to_rep(SubUniv, NextSubTerm)
> +		),
> +		deref_path(NextSubTerm, Tail, SubTerm)

This looks to be common code with part of deref_subterm_2 in browse.m,
but I can factor it out after you commit this diff.

I didn't look at the test cases all that closely, but they look OK.

I don't recall seeing anything in the diff that would change the behavior of
the abbreviated command "m" (for "mark") at the browser prompt.

If you want, you can address my comments after commit.

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