[m-rev.] for review: build subtrees based on desired nodes, instead of desired depth
Ian MacLarty
maclarty at cs.mu.OZ.AU
Sat Apr 16 16:58:22 AEST 2005
For review by anyone.
Estimated hours taken: 30
Branches: main
In the declarative debugger, instead of building new explicit subtrees down to
a fixed depth, allow the desired number of nodes in the subtree to be given and
estimate the depth that would produce such a subtree. This depth can be
estimated from the average branching factor of the tree and the desired number
of nodes to generate. The average branching factor, in turn, can be calculated
from the maximum depth of the subtree and the total number of events in the
subtree.
This is the first stage of a new method for determining how much of a
subtree to build in one go. The next stage will try to estimate how many
nodes should be in each subtree by considering how much memory is available
and how much memory each node consumes (this will be based on the nodes we have
materialized so far).
browser/declarative_debugger.m:
Accept a new argument from the C backend, DesiredSubtreeWeight, which
indicates how many nodes should be in newly materialized subtrees.
Pass this argument around where needed.
Calculate the maximum depth to build a new subtree to using the
given desired subtree weight and the average branching factor of the
implicit subtree. The average branching factor is calculated from
the number of events in the subtree and its maximum depth.
Return this maximum weight to the C backend.
browser/declarative_execution.m:
Instead of storing a boolean flag at CALL events to indicate that the
call is the root of an implicit subtree, store a maybe type,
which holds some information about the implicit subtree (at the moment
only the maximum depth).
Export a function to update the maximum call depth of an implicit
subtree.
browser/declarative_tree.m:
Add a predicate to retrieve information about an implicit subtree.
Export the predicate which calculates the weight of a subtree, to be
used in the calculation of the average branching factor of the
subtree.
trace/mercury_trace_declarative.c:
Hardcode the number of desired nodes in any subtree for now. The
next step will be to work this out from a desired amount of memory
usage.
Add a global variable, MR_edt_implicit_tree_max_depth which keeps
track of the maximum call depth in an implicit subtree.
Add a function to update the above global variable.
Update the maximum depth of the an implicit subtree for the
corresponding CALL node when an EXIT, FAIL or EXCP node is found
which is at the depth limit.
If a new explicit subtree is requested, set the step size to
the maximum required depth returned by the declarative debugger.
Fix a bug which caused the dd_dd command not to interactively trace
through the events generated by the declarative debugger.
Index: browser/declarative_debugger.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_debugger.m,v
retrieving revision 1.55
diff -u -r1.55 declarative_debugger.m
--- browser/declarative_debugger.m 6 Apr 2005 01:11:29 -0000 1.55
+++ browser/declarative_debugger.m 16 Apr 2005 06:52:38 -0000
@@ -250,15 +250,27 @@
% The analyser requires the back end to reproduce
% part of the annotated trace, with a greater
- % depth bound. The event number and sequence
- % number are for the final event required (the
- % first event required is the call event with
- % the same sequence number).
- % R is the node preceeding the call node. This is
- % needed so the root of the new tree can have the
- % correct preceding node.
+ % depth bound.
%
- ; require_subtree(event_number, sequence_number, R)
+ ; require_subtree(
+ %
+ % The event number and sequence
+ % number are for the final event required (the
+ % first event required is the call event with
+ % the same sequence number).
+ %
+ require_subtree_final_event :: event_number,
+ require_subtree_seqno :: sequence_number,
+
+ % The node preceeding the call node. This
+ % is needed so the root of the new tree can
+ % have the correct preceding node.
+ require_subtree_call_preceeding_node :: R,
+
+ % The maximum depth to build the new subtree
+ % to.
+ require_subtree_max_depth :: int
+ )
% The analyser requires events before and after the
% current set of materialized events to be generated.
@@ -274,7 +286,7 @@
diagnoser_state(R)::out) is det.
:- pred diagnosis(S::in, analysis_type(edt_node(R))::in, int::in, int::in,
- int::in, diagnoser_response(R)::out,
+ int::in, int::in, diagnoser_response(R)::out,
diagnoser_state(R)::in, diagnoser_state(R)::out,
browser_info.browser_persistent_state::in,
browser_info.browser_persistent_state::out,
@@ -309,7 +321,13 @@
:- import_module mdb.util.
:- import_module mdbcomp.prim_data.
-:- import_module exception, int, map, bool.
+:- import_module exception.
+:- import_module float.
+:- import_module int.
+:- import_module map.
+:- import_module bool.
+
+
unravel_decl_atom(DeclAtom, TraceAtom, IoActions) :-
(
@@ -363,8 +381,7 @@
Diagnoser = diagnoser(Analyser, Oracle).
diagnosis(Store, AnalysisType, UseOldIoActionMap, IoActionStart, IoActionEnd,
- Response, !Diagnoser, !Browser,
- !IO) :-
+ DesiredSubtreeWeight, Response, !Diagnoser, !Browser, !IO) :-
mdb.declarative_oracle.set_browser_state(!.Browser, !.Diagnoser ^
oracle_state, Oracle),
!:Diagnoser = !.Diagnoser ^ oracle_state := Oracle,
@@ -380,7 +397,8 @@
Analyser0, Analyser1),
!:Diagnoser = !.Diagnoser ^ analyser_state := Analyser1
),
- try_io(diagnosis_2(Store, AnalysisType, !.Diagnoser), Result, !IO),
+ try_io(diagnosis_2(Store, AnalysisType, DesiredSubtreeWeight,
+ !.Diagnoser), Result, !IO),
(
Result = succeeded({Response, !:Diagnoser})
;
@@ -397,34 +415,39 @@
!:Browser = mdb.declarative_oracle.get_browser_state(
!.Diagnoser ^ oracle_state).
-:- pred diagnosis_2(S::in, analysis_type(edt_node(R))::in,
+:- pred diagnosis_2(S::in, analysis_type(edt_node(R))::in, int::in,
diagnoser_state(R)::in,
{diagnoser_response(R), diagnoser_state(R)}::out,
io::di, io::uo) is cc_multi <= annotated_trace(S, R).
-diagnosis_2(Store, AnalysisType, Diagnoser0, {Response, Diagnoser}, !IO) :-
+diagnosis_2(Store, AnalysisType, DesiredSubtreeWeight, Diagnoser0,
+ {Response, Diagnoser}, !IO) :-
Analyser0 = Diagnoser0 ^ analyser_state,
start_or_resume_analysis(wrap(Store), AnalysisType,
AnalyserResponse, Analyser0, Analyser),
diagnoser_set_analyser(Analyser, Diagnoser0, Diagnoser1),
debug_analyser_state(Analyser, MaybeOrigin),
- handle_analyser_response(Store, AnalyserResponse, MaybeOrigin,
- Response, Diagnoser1, Diagnoser, !IO).
+ handle_analyser_response(Store, AnalyserResponse, DesiredSubtreeWeight,
+ MaybeOrigin, Response, Diagnoser1, Diagnoser, !IO).
:- pred handle_analyser_response(S::in, analyser_response(edt_node(R))::in,
- maybe(subterm_origin(edt_node(R)))::in, diagnoser_response(R)::out,
+ int::in, maybe(subterm_origin(edt_node(R)))::in,
+ diagnoser_response(R)::out,
diagnoser_state(R)::in, diagnoser_state(R)::out,
io::di, io::uo) is cc_multi <= annotated_trace(S, R).
-handle_analyser_response(_, no_suspects, _, no_bug_found, !Diagnoser, !IO) :-
+handle_analyser_response(_, no_suspects, _, _, no_bug_found, !Diagnoser, !IO)
+ :-
io.write_string("No bug found.\n", !IO).
-handle_analyser_response(Store, bug_found(Bug, Evidence), _, Response,
- !Diagnoser, !IO) :-
- confirm_bug(Store, Bug, Evidence, Response, !Diagnoser, !IO).
+handle_analyser_response(Store, bug_found(Bug, Evidence), DesiredSubtreeWeight,
+ _, Response, !Diagnoser, !IO) :-
+ confirm_bug(Store, Bug, Evidence, Response, DesiredSubtreeWeight,
+ !Diagnoser, !IO).
-handle_analyser_response(Store, oracle_question(Question), MaybeOrigin,
- Response, !Diagnoser, !IO) :-
+handle_analyser_response(Store, oracle_question(Question),
+ DesiredSubtreeWeight, MaybeOrigin, Response, !Diagnoser, !IO)
+ :-
diagnoser_get_oracle(!.Diagnoser, Oracle0),
debug_origin(Flag, !IO),
(
@@ -439,64 +462,76 @@
),
query_oracle(Question, OracleResponse, Oracle0, Oracle, !IO),
diagnoser_set_oracle(Oracle, !Diagnoser),
- handle_oracle_response(Store, OracleResponse, Response, !Diagnoser,
- !IO).
+ handle_oracle_response(Store, OracleResponse, Response,
+ DesiredSubtreeWeight, !Diagnoser, !IO).
-handle_analyser_response(Store, require_explicit_subtree(Node), _,
- Response, Diagnoser, Diagnoser, !IO) :-
+handle_analyser_response(Store, require_explicit_subtree(Node), DesiredWeight,
+ _, Response, Diagnoser, Diagnoser, !IO) :-
edt_subtree_details(Store, Node, Event, Seqno, CallPreceding),
- Response = require_subtree(Event, Seqno, CallPreceding).
+ (
+ trace_implicit_tree_info(wrap(Store), Node, ImplicitTreeInfo)
+ ->
+ trace_weight(wrap(Store), Node, TotalWeight, _),
+ MaxDepth = max_build_depth(ImplicitTreeInfo, TotalWeight,
+ DesiredWeight)
+ ;
+ throw(internal_error("handle_analyser_response",
+ "subtree requested for node which is not an " ++
+ "implicit root"))
+ ),
+ Response = require_subtree(Event, Seqno, CallPreceding, MaxDepth).
-handle_analyser_response(Store, require_explicit_supertree(Node), _,
+handle_analyser_response(Store, require_explicit_supertree(Node), _, _,
Response, Diagnoser, Diagnoser, !IO) :-
edt_subtree_details(Store, Node, Event, Seqno, _),
Response = require_supertree(Event, Seqno).
-handle_analyser_response(Store, revise(Question), _, Response, !Diagnoser, !IO)
- :-
+handle_analyser_response(Store, revise(Question), DesiredSubtreeWeight, _,
+ Response, !Diagnoser, !IO) :-
Oracle0 = !.Diagnoser ^ oracle_state,
revise_oracle(Question, Oracle0, Oracle),
!:Diagnoser = !.Diagnoser ^ oracle_state := Oracle,
- handle_analyser_response(Store, oracle_question(Question), no,
- Response, !Diagnoser, !IO).
+ handle_analyser_response(Store, oracle_question(Question),
+ DesiredSubtreeWeight, no, Response, !Diagnoser, !IO).
:- pred handle_oracle_response(S::in, oracle_response(edt_node(R))::in,
- diagnoser_response(R)::out, diagnoser_state(R)::in,
+ diagnoser_response(R)::out, int::in, diagnoser_state(R)::in,
diagnoser_state(R)::out, io::di, io::uo)
is cc_multi <= annotated_trace(S, R).
-handle_oracle_response(Store, oracle_answer(Answer), Response, !Diagnoser,
- !IO) :-
+handle_oracle_response(Store, oracle_answer(Answer), Response,
+ DesiredSubtreeWeight, !Diagnoser, !IO) :-
diagnoser_get_analyser(!.Diagnoser, Analyser0),
continue_analysis(wrap(Store), Answer, AnalyserResponse,
Analyser0, Analyser),
diagnoser_set_analyser(Analyser, !Diagnoser),
debug_analyser_state(Analyser, MaybeOrigin),
- handle_analyser_response(Store, AnalyserResponse, MaybeOrigin,
- Response, !Diagnoser, !IO).
+ handle_analyser_response(Store, AnalyserResponse, DesiredSubtreeWeight,
+ MaybeOrigin, Response, !Diagnoser, !IO).
-handle_oracle_response(Store, show_info(OutStream), Response, !Diagnoser, !IO)
- :-
+handle_oracle_response(Store, show_info(OutStream), Response,
+ DesiredSubtreeWeight, !Diagnoser, !IO) :-
diagnoser_get_analyser(!.Diagnoser, Analyser),
show_info(wrap(Store), OutStream, Analyser, AnalyserResponse, !IO),
debug_analyser_state(Analyser, MaybeOrigin),
- handle_analyser_response(Store, AnalyserResponse, MaybeOrigin,
- Response, !Diagnoser, !IO).
+ handle_analyser_response(Store, AnalyserResponse, DesiredSubtreeWeight,
+ MaybeOrigin, Response, !Diagnoser, !IO).
-handle_oracle_response(Store, exit_diagnosis(Node), Response, !Diagnoser, !IO)
- :-
+handle_oracle_response(Store, exit_diagnosis(Node), Response, _, !Diagnoser,
+ !IO) :-
edt_subtree_details(Store, Node, Event, _, _),
Response = symptom_found(Event).
-handle_oracle_response(_, abort_diagnosis, no_bug_found, !Diagnoser, !IO) :-
+handle_oracle_response(_, abort_diagnosis, no_bug_found, _, !Diagnoser, !IO) :-
io.write_string("Diagnosis aborted.\n", !IO).
:- pred confirm_bug(S::in, decl_bug::in, decl_evidence(T)::in,
- diagnoser_response(R)::out, diagnoser_state(R)::in,
+ diagnoser_response(R)::out, int::in, diagnoser_state(R)::in,
diagnoser_state(R)::out, io::di, io::uo) is cc_multi
<= annotated_trace(S, R).
-confirm_bug(Store, Bug, Evidence, Response, !Diagnoser, !IO) :-
+confirm_bug(Store, Bug, Evidence, Response, DesiredSubtreeWeight,
+ !Diagnoser, !IO) :-
diagnoser_get_oracle(!.Diagnoser, Oracle0),
oracle_confirm_bug(Bug, Evidence, Confirmation, Oracle0, Oracle, !IO),
diagnoser_set_oracle(Oracle, !Diagnoser),
@@ -506,23 +541,24 @@
Response = bug_found(Event)
;
Confirmation = overrule_bug,
- overrule_bug(Store, Response, !Diagnoser, !IO)
+ overrule_bug(Store, Response, DesiredSubtreeWeight,
+ !Diagnoser, !IO)
;
Confirmation = abort_diagnosis,
Response = no_bug_found
).
-:- pred overrule_bug(S::in, diagnoser_response(R)::out, diagnoser_state(R)::in,
- diagnoser_state(R)::out, io::di, io::uo) is cc_multi
- <= annotated_trace(S, R).
+:- pred overrule_bug(S::in, diagnoser_response(R)::out, int::in,
+ diagnoser_state(R)::in, diagnoser_state(R)::out, io::di, io::uo)
+ is cc_multi <= annotated_trace(S, R).
-overrule_bug(Store, Response, Diagnoser0, Diagnoser, !IO) :-
- Analyser0 = Diagnoser0 ^ analyser_state,
+overrule_bug(Store, Response, DesiredSubtreeWeight, !Diagnoser, !IO) :-
+ Analyser0 = !.Diagnoser ^ analyser_state,
revise_analysis(wrap(Store), AnalyserResponse, Analyser0, Analyser),
- Diagnoser1 = Diagnoser0 ^ analyser_state := Analyser,
+ !:Diagnoser = !.Diagnoser ^ analyser_state := Analyser,
debug_analyser_state(Analyser, MaybeOrigin),
- handle_analyser_response(Store, AnalyserResponse, MaybeOrigin,
- Response, Diagnoser1, Diagnoser, !IO).
+ handle_analyser_response(Store, AnalyserResponse, DesiredSubtreeWeight,
+ MaybeOrigin, Response, !Diagnoser, !IO).
%-----------------------------------------------------------------------------%
@@ -571,43 +607,46 @@
:- pragma export(mdb.declarative_debugger.divide_and_query_search_mode = out,
"MR_DD_decl_divide_and_query_search_mode").
- % Export a monomorphic version of diagnosis/10 that passes a newly
- % materialized tree for use with the C backend code.
+ % Export a monomorphic version of diagnosis/10 that accepts a newly
+ % materialized tree, for use with the C backend code.
%
:- pred diagnosis_new_tree(trace_node_store::in, trace_node_id::in,
- int::in, int::in, int::in, diagnoser_response(trace_node_id)::out,
+ int::in, int::in, int::in, int::in,
+ diagnoser_response(trace_node_id)::out,
diagnoser_state(trace_node_id)::in,
diagnoser_state(trace_node_id)::out,
browser_info.browser_persistent_state::in,
browser_info.browser_persistent_state::out, io::di, io::uo)
is cc_multi.
-:- pragma export(diagnosis_new_tree(in, in, in, in, in, out, in, out, in, out,
- di, uo), "MR_DD_decl_diagnosis_new_tree").
+:- pragma export(diagnosis_new_tree(in, in, in, in, in, in, out, in, out, in,
+ out, di, uo), "MR_DD_decl_diagnosis_new_tree").
diagnosis_new_tree(Store, Node, UseOldIoActionMap, IoActionStart, IoActionEnd,
- Response, !State, !Browser, !IO) :-
+ DesiredSubtreeWeight, Response, !State, !Browser, !IO) :-
diagnosis(Store, new_tree(dynamic(Node)), UseOldIoActionMap,
- IoActionStart, IoActionEnd, Response, !State, !Browser, !IO).
+ IoActionStart, IoActionEnd, DesiredSubtreeWeight, Response,
+ !State, !Browser, !IO).
% Export a monomorphic version of diagnosis/10 that requests the
% continuation of a previously suspended declarative debugging session.
%
:- pred diagnosis_resume_previous(trace_node_store::in, int::in, int::in,
- int::in, diagnoser_response(trace_node_id)::out,
+ int::in, int::in, diagnoser_response(trace_node_id)::out,
diagnoser_state(trace_node_id)::in,
diagnoser_state(trace_node_id)::out,
browser_info.browser_persistent_state::in,
browser_info.browser_persistent_state::out, io::di, io::uo)
is cc_multi.
-:- pragma export(diagnosis_resume_previous(in, in, in, in,out, in, out, in,
+:- pragma export(diagnosis_resume_previous(in, in, in, in, in, out, in, out, in,
out, di, uo), "MR_DD_decl_diagnosis_resume_previous").
diagnosis_resume_previous(Store, UseOldIoActionMap, IoActionStart, IoActionEnd,
- Response, !State, !Browser, !IO) :-
+ DesiredSubtreeWeight, Response, !State, !Browser, !IO) :-
diagnosis(Store, resume_previous, UseOldIoActionMap, IoActionStart,
- IoActionEnd, Response, !State, !Browser, !IO).
+ IoActionEnd, DesiredSubtreeWeight, Response, !State, !Browser,
+ !IO).
% Export some predicates so that C code can interpret the
% diagnoser response.
@@ -635,14 +674,14 @@
diagnoser_no_bug_found(no_bug_found).
:- pred diagnoser_require_subtree(diagnoser_response(trace_node_id)::in,
- event_number::out, sequence_number::out, trace_node_id::out)
+ event_number::out, sequence_number::out, trace_node_id::out, int::out)
is semidet.
-:- pragma export(diagnoser_require_subtree(in, out, out, out),
+:- pragma export(diagnoser_require_subtree(in, out, 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,
+ MaxDepth), Event, SeqNo, CallPreceding, MaxDepth).
:- pred diagnoser_require_supertree(diagnoser_response(trace_node_id)::in,
event_number::out, sequence_number::out) is semidet.
@@ -822,3 +861,88 @@
").
debug_origin(_, !IO) :-
private_builtin.sorry("declarative_debugger.debug_origin").
+
+%-----------------------------------------------------------------------------%
+
+:- func max_build_depth(implicit_tree_info, int, int) = int.
+
+max_build_depth(implicit_tree_info(MaxDepth), TotalWeight, DesiredWeight)
+ = Depth :-
+ BranchingFactor = average_branching_factor(MaxDepth, TotalWeight),
+ Depth = depth_for_desired_weight(DesiredWeight, BranchingFactor).
+
+:- func average_branching_factor(int, int) = float.
+
+average_branching_factor(Depth, Weight) =
+ %
+ % The relationship between the number of nodes in a tree, n,
+ % the average branching factor of a tree, b, and the depth of the
+ % tree, d, is given by n = 1 + b + b^2 + ... + b^(d-1),
+ % so to find b, we must find the root of
+ % f(b) = 1 - n + b + b^2 + ... + b^(d-1).
+ %
+ binary_converge_to_root(
+ poly_with_unit_coefficients(Depth - 1, 1.0 - float(Weight)),
+ 0.1, 1.0, 10.0, 1000.0, 50).
+
+:- func depth_for_desired_weight(int, float) = int.
+
+depth_for_desired_weight(Weight, BranchingFactor) =
+ %
+ % To find the depth of a tree given it's average branching
+ % factor, b, and the number of nodes in the tree, n, we must find
+ % the root of f(d) = 1 - n + b + b^2 + ... + b^(d-1).
+ %
+ round_to_int(binary_converge_to_root(
+ (func(Depth) =
+ poly_with_unit_coefficients(round_to_int(Depth) - 1,
+ 1.0 - float(Weight), BranchingFactor)
+ ),
+ 1.0, 1.0, 100.0, 1000000.0, 50)).
+
+ % poly_with_unit_coefficients(N, C, X) = C + X + X^2 + ... + X^N.
+ %
+:- func poly_with_unit_coefficients(int, float, float) = float.
+
+poly_with_unit_coefficients(Degree, Constant, X)
+ = poly_with_unit_coefficients_2(Degree, 1.0, Constant, X).
+
+:- func poly_with_unit_coefficients_2(int, float, float, float) = float.
+
+poly_with_unit_coefficients_2(Degree, PrevTerm, TotalSoFar, X) = Y :-
+ (
+ Degree > 0
+ ->
+ NewTerm = PrevTerm * X,
+ Y = poly_with_unit_coefficients_2(Degree - 1, NewTerm,
+ TotalSoFar + NewTerm, X)
+ ;
+ Y = TotalSoFar
+ ).
+
+ % Find the root of a strictly increasing continuous real function
+ % using a binary search. Newton's method converges quicker, but
+ % the evaluation of the derivative can cause infinite floating
+ % point values.
+ %
+:- func binary_converge_to_root(func(float) = float, float, float, float,
+ float, int) = float.
+
+binary_converge_to_root(F, Precision, Left, Middle, Right, MaxIterations)
+ = Root :-
+ ( MaxIterations > 0 ->
+ Y = F(Middle),
+ ( Precision > float.abs(Y) ->
+ Root = Middle
+ ; Y > 0.0 ->
+ Root = binary_converge_to_root(F, Precision, Left,
+ Left + (Middle - Left) / 2.0, Middle,
+ MaxIterations - 1)
+ ;
+ Root = binary_converge_to_root(F, Precision, Middle,
+ Middle + (Right - Middle) / 2.0, Right,
+ MaxIterations - 1)
+ )
+ ;
+ Root = Middle
+ ).
Index: browser/declarative_execution.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_execution.m,v
retrieving revision 1.42
diff -u -r1.42 declarative_execution.m
--- browser/declarative_execution.m 12 Apr 2005 01:53:54 -0000 1.42
+++ browser/declarative_execution.m 16 Apr 2005 06:14:35 -0000
@@ -49,8 +49,12 @@
% Call sequence number.
call_event :: event_number,
% Trace event number.
- call_at_max_depth :: bool,
- % At the maximum depth?
+ call_at_max_depth :: maybe(implicit_tree_info),
+ % yes if the node is the root
+ % of an implicitly represented
+ % tree. Some information about
+ % the implicit tree is also
+ % stored.
call_return_label :: maybe(label_layout),
% The return label, if there
% is one.
@@ -200,6 +204,11 @@
% data structures.
).
+:- type implicit_tree_info
+ ---> implicit_tree_info(
+ max_depth :: int
+ ).
+
:- func get_trace_exit_atom(trace_node(R)) = trace_atom.
:- mode get_trace_exit_atom(in(trace_node_exit)) = out is det.
:- mode get_trace_exit_atom(in) = out is semidet.
@@ -1057,6 +1066,38 @@
%
set_trace_node_arg(Call1, 1, Last, Call).
+:- func call_node_update_implicit_tree_info(trace_node(trace_node_id)::di,
+ int::in) = (trace_node(trace_node_id)::out) is det.
+
+:- pragma export(call_node_update_implicit_tree_info(di, in) = out,
+ "MR_DD_call_node_update_implicit_tree_info").
+
+call_node_update_implicit_tree_info(Call0, MaxDepth) = Call :-
+ (
+ MaybeImplicitTreeInfo = Call0 ^ call_at_max_depth
+ ->
+ (
+ MaybeImplicitTreeInfo = no,
+ throw(internal_error(
+ "call_node_update_implicit_tree_info",
+ "not at max depth"))
+ ;
+ MaybeImplicitTreeInfo =
+ yes(implicit_tree_info(MaxDepth0)),
+ (
+ MaxDepth > MaxDepth0
+ ->
+ Call = Call0 ^ call_at_max_depth :=
+ yes(implicit_tree_info(MaxDepth))
+ ;
+ Call = Call0
+ )
+ )
+ ;
+ throw(internal_error("call_node_update_implicit_tree_info",
+ "not a CALL node"))
+ ).
+
:- func cond_node_set_status(trace_node(trace_node_id)::di, goal_status::di)
= (trace_node(trace_node_id)::out) is det.
@@ -1238,16 +1279,26 @@
%
:- func construct_call_node(trace_node_id, list(trace_atom_arg),
- sequence_number, event_number, bool, maybe(label_layout),
- label_layout, int) = trace_node(trace_node_id).
+ sequence_number, event_number, bool, maybe(label_layout), label_layout,
+ int) = trace_node(trace_node_id).
:- pragma export(construct_call_node(in, in, in, in, in, in, in, in) = out,
"MR_DD_construct_call_node").
-construct_call_node(Preceding, AtomArgs, SeqNo, EventNo, MaxDepth,
+construct_call_node(Preceding, AtomArgs, SeqNo, EventNo, AtMaxDepth,
MaybeReturnLabel, Label, IoSeqNum) = Call :-
- Call = call(Preceding, Answer, AtomArgs, SeqNo, EventNo, MaxDepth,
- MaybeReturnLabel, Label, IoSeqNum),
- null_trace_node_id(Answer).
+ (
+ AtMaxDepth = no,
+ MaybeImplicitTreeInfo = no
+ ;
+ AtMaxDepth = yes,
+ % The maximum depth of the implicit tree will be updated
+ % when the corresponding EXIT, FAIL or EXCP event occurs,
+ % so for now we just set it to 0.
+ MaybeImplicitTreeInfo = yes(implicit_tree_info(0))
+ ),
+ null_trace_node_id(LastInterface),
+ Call = call(Preceding, LastInterface, AtomArgs, SeqNo, EventNo,
+ MaybeImplicitTreeInfo, MaybeReturnLabel, Label, IoSeqNum).
:- func make_yes_maybe_label(label_layout) = maybe(label_layout).
:- pragma export(make_yes_maybe_label(in) = out, "MR_DD_make_yes_maybe_label").
@@ -1260,7 +1311,7 @@
make_no_maybe_label = no.
:- func construct_exit_node(trace_node_id, trace_node_id, trace_node_id,
- list(trace_atom_arg), event_number, label_layout, int)
+ list(trace_atom_arg), event_number, label_layout, int)
= trace_node(trace_node_id).
:- pragma export(construct_exit_node(in, in, in, in, in, in, in) = out,
"MR_DD_construct_exit_node").
Index: browser/declarative_tree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_tree.m,v
retrieving revision 1.26
diff -u -r1.26 declarative_tree.m
--- browser/declarative_tree.m 11 Apr 2005 06:43:34 -0000 1.26
+++ browser/declarative_tree.m 16 Apr 2005 05:11:43 -0000
@@ -40,6 +40,12 @@
:- pred trace_atom_subterm_is_ground(trace_atom::in, arg_pos::in,
term_path::in) is semidet.
+:- pred trace_implicit_tree_info(wrap(S)::in, edt_node(R)::in,
+ implicit_tree_info::out) is semidet <= annotated_trace(S, R).
+
+:- pred trace_weight(wrap(S)::in, edt_node(R)::in, int::out, int::out)
+ is det <= annotated_trace(S, R).
+
%-----------------------------------------------------------------------------%
:- implementation.
@@ -305,8 +311,10 @@
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_implicit_tree_info(wrap(Store), dynamic(Ref), ImplicitTreeInfo) :-
+ get_edt_call_node(Store, Ref, CallId),
+ call_node_from_id(Store, CallId, CallNode),
+ CallNode ^ call_at_max_depth = yes(ImplicitTreeInfo).
trace_weight(Store, NodeId, Weight, ExcessWeight) :-
node_events(Store, NodeId, 0, Weight, no, 0, 0, ExcessWeight).
Index: trace/mercury_trace_declarative.c
===================================================================
RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_declarative.c,v
retrieving revision 1.85
diff -u -r1.85 mercury_trace_declarative.c
--- trace/mercury_trace_declarative.c 13 Apr 2005 03:50:55 -0000 1.85
+++ trace/mercury_trace_declarative.c 16 Apr 2005 06:24:31 -0000
@@ -110,6 +110,13 @@
"Do you wish to proceed with the retry? "
/*
+** The desired number of nodes to add to the annotated trace when
+** materializing a new subtree.
+*/
+
+#define MR_TRACE_DESIRED_SUBTREE_NODES 1000
+
+/*
** The declarative debugger back end is controlled by the
** settings of the following variables. They are set in
** MR_trace_start_decl_debug when the back end is started. They
@@ -195,6 +202,15 @@
static MR_Unsigned MR_edt_max_depth;
/*
+** This global is used to keep track of the maximum depth of any implicit
+** subtrees in the EDT. The depth of the implicit trees are then used to
+** calculate the average branching factor which can be used to estimate how
+** deep to build an implicit subtree if it needs to be materialized.
+*/
+
+static MR_Unsigned MR_edt_implicit_tree_max_depth;
+
+/*
** The declarative debugger ignores modules that were not compiled with
** the required information. However, this may result in incorrect
** assumptions being made about the code, so the debugger gives a warning
@@ -338,6 +354,8 @@
static MR_Unsigned MR_trace_calculate_event_depth(
MR_Event_Info *event_info);
static void MR_trace_construct_node(MR_Event_Info *event_info);
+static void MR_trace_update_max_implicit_subtree_depth(
+ MR_Event_Info *event_info);
MR_bool MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
@@ -377,6 +395,8 @@
MR_trace_edt_build_sanity_check(event_info, entry);
+ MR_trace_update_max_implicit_subtree_depth(event_info);
+
if (! MR_trace_include_event(entry, event_info, &jumpaddr)) {
return jumpaddr;
}
@@ -426,6 +446,23 @@
}
static void
+MR_trace_update_max_implicit_subtree_depth(MR_Event_Info *event_info)
+{
+ /*
+ ** Set the maximum depth to the call depth if either the
+ ** call depth is greater than the current maximum, or
+ ** we are entering the top of an implicit subtree.
+ */
+ if ((event_info->MR_call_depth > MR_edt_implicit_tree_max_depth)
+ || (MR_edt_depth == MR_edt_max_depth
+ && (event_info->MR_trace_port == MR_PORT_CALL
+ || event_info->MR_trace_port == MR_PORT_REDO)))
+ {
+ MR_edt_implicit_tree_max_depth = event_info->MR_call_depth;
+ }
+}
+
+static void
MR_trace_edt_build_sanity_check(MR_Event_Info *event_info,
const MR_Proc_Layout *entry)
{
@@ -801,6 +838,18 @@
call = MR_trace_matching_call(prev);
MR_decl_checkpoint_match(call);
+
+ /*
+ ** We need to add 1 to MR_edt_depth since this is an EXIT
+ ** event, so 1 would already have been subtracted from MR_edt_depth
+ ** in MR_trace_calculate_event_depth.
+ */
+ if (MR_edt_depth + 1 == MR_edt_max_depth) {
+ MR_DD_call_node_update_implicit_tree_info(call,
+ MR_edt_implicit_tree_max_depth
+ - event_info->MR_call_depth);
+ }
+
MR_TRACE_CALL_MERCURY(
last_interface = MR_DD_call_node_get_last_interface(
(MR_Word) call);
@@ -880,6 +929,17 @@
}
MR_decl_checkpoint_match(call);
+ /*
+ ** We need to add 1 to MR_edt_depth since this is a FAIL
+ ** event, so 1 would already have been subtracted from MR_edt_depth
+ ** in MR_trace_calculate_event_depth.
+ */
+ if (MR_edt_depth + 1 == MR_edt_max_depth) {
+ MR_DD_call_node_update_implicit_tree_info(call,
+ MR_edt_implicit_tree_max_depth
+ - event_info->MR_call_depth);
+ }
+
MR_TRACE_CALL_MERCURY(
redo = MR_DD_call_node_get_last_interface((MR_Word) call);
node = (MR_Trace_Node) MR_DD_construct_fail_node(
@@ -903,6 +963,17 @@
call = MR_trace_matching_call(prev);
MR_decl_checkpoint_match(call);
+ /*
+ ** We need to add 1 to MR_edt_depth since this is an EXCP
+ ** event, so 1 would already have been subtracted from MR_edt_depth
+ ** in MR_trace_calculate_event_depth.
+ */
+ if (MR_edt_depth + 1 == MR_edt_max_depth) {
+ MR_DD_call_node_update_implicit_tree_info(call,
+ MR_edt_implicit_tree_max_depth
+ - event_info->MR_call_depth);
+ }
+
MR_TRACE_CALL_MERCURY(
last_interface = MR_DD_call_node_get_last_interface(
(MR_Word) call);
@@ -1762,6 +1833,9 @@
MR_debug_enabled = MR_TRUE;
MR_update_trace_func_enabled();
MR_trace_decl_mode = MR_TRACE_INTERACTIVE;
+ } else {
+ MR_debug_enabled = MR_FALSE;
+ MR_update_trace_func_enabled();
}
io_start = MR_edt_start_io_counter;
@@ -1780,15 +1854,13 @@
MR_io_action_map_cache_end = io_end;
}
- MR_debug_enabled = MR_FALSE;
- MR_update_trace_func_enabled();
-
MR_TRACE_CALL_MERCURY(
if (new_tree == MR_TRUE) {
MR_DD_decl_diagnosis_new_tree(MR_trace_node_store,
root, use_old_io_map,
MR_io_action_map_cache_start,
MR_io_action_map_cache_end,
+ MR_TRACE_DESIRED_SUBTREE_NODES,
&response, MR_trace_front_end_state,
&MR_trace_front_end_state,
MR_trace_browser_persistent_state,
@@ -1799,6 +1871,7 @@
MR_trace_node_store, MR_FALSE,
MR_io_action_map_cache_start,
MR_io_action_map_cache_end,
+ MR_TRACE_DESIRED_SUBTREE_NODES,
&response, MR_trace_front_end_state,
&MR_trace_front_end_state,
MR_trace_browser_persistent_state,
@@ -1813,23 +1886,19 @@
require_subtree = MR_DD_diagnoser_require_subtree(response,
(MR_Integer *) &final_event,
(MR_Integer *) &topmost_seqno,
- (MR_Trace_Node *) &call_preceding);
+ (MR_Trace_Node *) &call_preceding,
+ (MR_Integer *) &MR_edt_depth_step_size);
require_supertree = MR_DD_diagnoser_require_supertree(response,
(MR_Integer *) &final_event,
(MR_Integer *) &topmost_seqno);
);
- MR_debug_enabled = MR_TRUE;
- MR_update_trace_func_enabled();
-
/*
** Turn off interactive debugging after the diagnosis in case a new
** explicit subtree or supertree needs to be constructed.
*/
- if (MR_trace_decl_in_dd_dd_mode) {
- MR_debug_enabled = MR_FALSE;
- MR_trace_decl_mode = MR_TRACE_DECL_DEBUG;
- }
+ MR_debug_enabled = MR_FALSE;
+ MR_trace_decl_mode = MR_TRACE_DECL_DEBUG;
MR_trace_call_seqno = event_details->MR_call_seqno;
MR_trace_call_depth = event_details->MR_call_depth;
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the reviews
mailing list