[m-rev.] for review: accurately calculate depth to build subtrees to
Ian MacLarty
maclarty at cs.mu.OZ.AU
Thu May 19 20:50:12 AEST 2005
On Fri, 13 May 2005, Julien Fischer wrote:
> >
> > Okay, how about if I'm building a supertree I just print a dot every
> > second? That would be pretty easy to do. I'll do that and also add a
> > summary of how subtrees and supertrees are built to the top of
> > mercury_trace_declarative.c and then I'll post the interdiff for
> > review.
> >
> Yes, something like that. I think that it is important that
> the user experience here is consistent (or at least as consistent
> as is easily possible.)
>
Here's the interdiff. I have also put an overview of the backend in
mercury_trace_declarative.c and removed some of the complexity around depth
limits by making edt_dependency check if an explicit subtree is required,
instead of relying on the backend to ensure that the children of nodes at the
depth limit are materialized.
diff -bu browser/declarative_tree.m browser/declarative_tree.m
--- browser/declarative_tree.m 10 May 2005 04:57:54 -0000
+++ browser/declarative_tree.m 19 May 2005 10:18:35 -0000
@@ -728,7 +728,10 @@
maybe(proc_rep)
% The body of the procedure indicated
% by start_loc.
- ).
+ )
+ % An explicit subtree is required before the
+ % chain start can be calculated.
+ ; require_explicit_subtree.
:- type start_loc(R)
---> cur_goal
@@ -755,8 +758,15 @@
trace_subterm_mode(wrap(Store), dynamic(Ref), ArgPos, TermPath, Mode) :-
find_chain_start(Store, Ref, ArgPos, TermPath, ChainStart),
+ (
ChainStart = chain_start(StartLoc, _, _, _, _, _),
- Mode = start_loc_to_subterm_mode(StartLoc).
+ Mode = start_loc_to_subterm_mode(StartLoc)
+ ;
+ ChainStart = require_explicit_subtree,
+ % The only time a subtree will be required is if the
+ % mode of the subterm is output.
+ Mode = subterm_out
+ ).
:- pred trace_dependency(wrap(S)::in, edt_node(R)::in, arg_pos::in,
term_path::in, subterm_mode::out, subterm_origin(edt_node(R))::out)
@@ -764,6 +774,7 @@
trace_dependency(wrap(Store), dynamic(Ref), ArgPos, TermPath, Mode, Origin) :-
find_chain_start(Store, Ref, ArgPos, TermPath, ChainStart),
+ (
ChainStart = chain_start(StartLoc, ArgNum, TotalArgs, NodeId,
StartPath, MaybeProcRep),
Mode = start_loc_to_subterm_mode(StartLoc),
@@ -809,12 +823,20 @@
MaybeClosure = no,
AdjustedTermPath = TermPath
),
- traverse_primitives(Primitives, Var, AdjustedTermPath,
- Store, ProcRep, Origin)
+ traverse_primitives(Primitives, Var,
+ AdjustedTermPath, Store, ProcRep,
+ Origin)
;
MaybePrims = no,
Origin = not_found
)
+ )
+ ;
+ ChainStart = require_explicit_subtree,
+ Origin = require_explicit_subtree,
+ % The only time a subtree will be required is if the
+ % mode of the subterm is output.
+ Mode = subterm_out
).
:- pred find_chain_start(S::in, R::in, arg_pos::in, term_path::in,
@@ -831,8 +853,14 @@
find_chain_start_inside(Store, CallId, CallNode,
ArgPos, ChainStart)
; trace_atom_subterm_is_ground(ExitAtom, ArgPos, TermPath) ->
- find_chain_start_outside(CallNode, Node, ArgPos,
- ChainStart)
+ (
+ not_at_depth_limit(Store, CallId)
+ ->
+ find_chain_start_outside(CallNode, Node,
+ ArgPos, ChainStart)
+ ;
+ ChainStart = require_explicit_subtree
+ )
;
throw(internal_error("find_chain_start",
"unbound wrong answer term"))
diff -bu trace/mercury_trace_declarative.c trace/mercury_trace_declarative.c
--- trace/mercury_trace_declarative.c 13 May 2005 02:40:38 -0000
+++ trace/mercury_trace_declarative.c 19 May 2005 10:26:21 -0000
@@ -1,4 +1,7 @@
/*
+** vim: ts=4 sw=4 expandtab
+*/
+/*
** Copyright (C) 1998-2005 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.
@@ -27,16 +30,84 @@
** than analyzing them for bugs.
**
** The backend decides which events should be included in the annotated trace.
-** Given a final event the backend can either build the
-** annotated trace for the subtree rooted at the final event down to a specified
-** depth limit, or can build the tree a specified number of ancestors above the
-** given event, with the given event as an implicit root of the existing trace.
+** Given a final event the backend can either build the annotated trace for the
+** subtree rooted at the final event down to a specified depth limit, or can
+** build the tree a specified number of ancestors above the given event.
**
** The backend can be called multiple times to materialize different portions
** of the annotated trace. It is the responsibility of the frontend to
** connect the various portions of the annotated trace together into a
** complete tree. This is done in declarative_edt.m.
**
+**
+** Overview of the declarative debugger backend
+** --------------------------------------------
+**
+** Building of a new portion of the annotated trace is started when either the
+** user issues a `dd' command from the procedural debugger, or the
+** frontend requests that a new explicit subtree or supertree be built.
+**
+** Initially the trace is materialized down to a predefined depth, given
+** by the value of MR_edt_default_depth_limit. We retry to the CALL event
+** corresponding to the EXIT, FAIL or EXCP event where the `dd' command was
+** issued and rerun the program, collecting all events above the depth limit.
+** Once we get to the EXIT, FAIL or EXCP event where the `dd' command was
+** issued, we call the front end (in browser/declarative_debugger.m) and
+** ask it to analyse the generated trace. The frontend then returns with one
+** of three possible responses:
+**
+** 1. The front end wants control to return to the procedural debugger.
+** This could be because the bug has been found, or the user has
+** exited the declarative debugging session.
+** 2. The front end wants the subtree of a specific node in the annotated
+** trace. Here the frontend will tell the backend to what depth it
+** wants the new subtree built to.
+** 3. The front end wants nodes generated above the currently materialized
+** portion of the annotated trace (refered to here as a supertree).
+**
+** In case 1 the frontend may want control returned to the procedural debugger
+** at an event other than the event where the `dd' command was issued. If this
+** is the case then we perform a retry to get to an event before the desired
+** event and then simulate a `goto' command, so that mdb prompts the user
+** at the desired event.
+**
+** In case 2 the frontend will supply the event number and call sequence
+** number of the EXIT, FAIL or EXCP event at the root of the required subtree.
+** The backend will then retry to a CALL event before or equal to the CALL
+** with the given sequence number. The program is then reexecuted and nodes
+** are added to the annotated trace to the depth limit specified by the
+** frontend.
+**
+** If, while the program is being reexecuted, the call depth exceeds the
+** depth limit, then we record, in an array, how many events are at each
+** depth below the depth limit. The data collected is used to populate
+** a field at each CALL event which is the root of an implicit (unmaterialized)
+** subtree in the annotated trace. The field (called the ideal depth) gives
+** the maximum depth the implicit subtree needs to be built to so that no more
+** than MR_edt_desired_nodes_in_subtree nodes are materialized. The frontend
+** passes the ideal depth to the backend when requesting a new subtree.
+**
+** In case 3 the frontend will supply the event number and call sequence
+** number of the EXIT, FAIL or EXCP event at the root of the currently
+** materialized tree. As with case 2 the backend will retry to a CALL before
+** the given call sequence number and start rexecuting the program, however
+** no events are added to the annotated trace yet. When execution reaches the
+** CALL event with the sequence number given by the frontend, another retry is
+** performed to get MR_edt_default_depth_limit levels above the currently
+** materialized tree. Execution is then restarted from this point and
+** collection of events begins. Events are collected down to the depth of
+** the root of the previously materialized tree as illustrated in the
+** following diagram.
+**
+** /\ |
+** / \ |- Newly materialized supertree
+** / \ |
+** /\ |
+** / \ |
+** / \ |- Previously materialized tree
+** / \ |
+** / \ |
+**
*/
#include "mercury_imp.h"
@@ -137,8 +208,7 @@
** If we are building a subtree then reaching this event will cause the
** declarative debugger to continue its analysis. Reaching this event means
** generation of the desired subtree is complete. This variable is not used
-** when building a new explicit supertree (a supertree is a tree above the
-** currently materialized portion of the annotated trace).
+** when building a new explicit supertree.
*/
static MR_Unsigned MR_edt_last_event;
@@ -219,6 +289,13 @@
static MR_Unsigned MR_edt_start_time;
/*
+** This global keeps track of how many ticks have been printed so far in
+** the progress message.
+*/
+
+static MR_Unsigned MR_edt_progress_last_tick = 0;
+
+/*
** The first event executed during the current re-execution.
*/
static MR_Unsigned MR_edt_first_event;
@@ -384,7 +462,9 @@
MR_Event_Info *event_info, MR_Unsigned depth);
static void MR_trace_maybe_update_implicit_tree_ideal_depth(
MR_Unsigned depth, MR_Trace_Node call);
-static void MR_trace_maybe_show_progress(MR_Unsigned event_number);
+static void MR_trace_maybe_show_progress(
+ MR_Unsigned event_number);
+static void MR_trace_finish_progress(void);
static void MR_trace_init_implicit_subtree_counters(
MR_Unsigned size);
static void MR_trace_reset_implicit_subtree_counters(void);
@@ -401,15 +481,9 @@
/*
** We filter out events which are deeper than the limit given by
** MR_edt_max_depth. These events are implicitly represented in the structure
-** being built. Adding 1 to the depth limit ensures we get all the interface
-** events inside a call at the depth limit. We need these to build the correct
-** contour. Note that interface events captured at the maximum depth plus one
-** will have their at-depth-limit flag set to no. This is not a problem, since
-** the parent's flag will be yes. There is no chance that the analyser could
-** ask for the children of an interface event captured at the maximum depth
-** plus one without the annotated trace being rebuilt from the parent first.
+** being built.
*/
-#define MR_TRACE_EVENT_TOO_DEEP(depth) (depth > MR_edt_max_depth + 1)
+#define MR_TRACE_EVENT_TOO_DEEP(depth) (depth > MR_edt_max_depth)
/*
** This function is called for every traced event when building the
@@ -471,6 +545,9 @@
{
MR_trace_free_implicit_subtree_counters();
MR_decl_maybe_print_edt_stats();
+ if (MR_edt_progress_last_tick > 0) {
+ MR_trace_finish_progress();
+ }
/*
** Call the front end.
@@ -1979,15 +2056,11 @@
/*
** The front end requires a subtree to be made explicit.
** Restart the declarative debugger with the appropriate depth
- ** limit. We subtract 1 from the depth limit, since nodes will
- ** be materialized one level below the depth limit. This is
- ** done so that the correct contour can be built at the depth
- ** limit. See the comment for the definition of
- ** MR_TRACE_EVENT_TOO_DEEP.
+ ** limit.
*/
return MR_trace_restart_decl_debug(call_preceding,
final_event, topmost_seqno, MR_FALSE,
- requested_subtree_depth - 1, cmd, event_info,
+ requested_subtree_depth, cmd, event_info,
event_details);
}
@@ -2233,20 +2306,15 @@
if (total > MR_edt_desired_nodes_in_subtree) {
/*
** Since we have gone over the desired number of nodes,
- ** the ideal depth is depth - 1. We want the depth to
- ** be at least 2 because if it is 1, the root of the
- ** new tree will have its at-depth-limit flag set.
+ ** the ideal depth is depth - 1. Note that we want the
+ ** depth limit to be at least one, otherwise we won't
+ ** add any new nodes to the annotated trace.
*/
- return (depth - 1) < 2 ? 2 : (depth - 1);
+ return (depth - 1) < 1 ? 1 : (depth - 1);
}
if (events_at_depth == 0) {
- /*
- ** This implicit subtree can be fully materialized.
- ** We add 1 in the unlikely event that
- ** MR_edt_implicit_subtree_num_counters is 1.
- */
- return MR_edt_implicit_subtree_num_counters + 1;
+ return MR_edt_implicit_subtree_num_counters;
}
depth++;
@@ -2256,7 +2324,7 @@
** We didn't record the number of events at greater depths, so
** be conservative and return the biggest depth we recorded up to.
*/
- return (depth - 1) < 2 ? 2 : (depth - 1);
+ return (depth - 1) < 1 ? 1 : (depth - 1);
}
/*
@@ -2296,26 +2364,11 @@
static void
MR_trace_maybe_show_progress(MR_Unsigned event_number)
{
- static MR_Unsigned last_tick = 0;
MR_Unsigned current_tick;
- /*
- ** We can't show progress when building a supertree since we don't
- ** know what the final event will be.
- ** XXX In future, when building a supertree we should not
- ** reexecute the part of the program already materialized in the
- ** annotated trace, but should instead get the output arguments
- ** from the annotated trace and put them in the correct registers.
- ** This would mean we could build small supertrees without reexecuting
- ** all the events under the supertree everytime, so building of
- ** supertrees should be quick and we wouldn't ever need to show
- ** progress anyway.
- */
- if (!MR_edt_building_supertree && (
- (event_number % MR_DECL_PROGRESS_CHECK_INTERVAL == 0)
- || event_number == MR_edt_last_event))
- {
- if (last_tick == 0 &&
+ if (event_number % MR_DECL_PROGRESS_CHECK_INTERVAL == 0) {
+ if (! MR_edt_building_supertree) {
+ if (MR_edt_progress_last_tick == 0 &&
(MR_edt_start_time + MR_DECL_DISPLAY_PROGRESS_DELAY
< MR_get_user_cpu_miliseconds()))
{
@@ -2325,26 +2378,56 @@
** We count the initial progress message as the first
** tick.
*/
- last_tick = 1;
- } else if (last_tick > 0) {
+ MR_edt_progress_last_tick = 1;
+ } else if (MR_edt_progress_last_tick > 0) {
current_tick = ((event_number - MR_edt_first_event)
* MR_DECL_PROGRESS_TOTAL)
/ (MR_edt_last_event - MR_edt_first_event);
- if (current_tick != last_tick) {
- for (; last_tick < current_tick; last_tick++) {
+ if (current_tick != MR_edt_progress_last_tick) {
+ for (; MR_edt_progress_last_tick < current_tick;
+ MR_edt_progress_last_tick++)
+ {
fprintf(MR_mdb_out,
MR_DECL_PROGRESS_TICK_STRING);
fflush(MR_mdb_out);
}
- if (current_tick == MR_DECL_PROGRESS_TOTAL) {
- fprintf(MR_mdb_out, "\n");
- last_tick = 0;
}
}
+ } else {
+ /*
+ ** If we are building a supertree we don't know what the
+ ** final event will be, so we just show a tick every
+ ** MR_DECL_DISPLAY_PROGRESS_DELAY miliseconds, so at least
+ ** the user knows something is happening.
+ */
+ if (MR_edt_progress_last_tick == 0 &&
+ (MR_edt_start_time + MR_DECL_DISPLAY_PROGRESS_DELAY
+ < MR_get_user_cpu_miliseconds()))
+ {
+ fprintf(MR_mdb_out, MR_DECL_PROGRESS_MESSAGE);
+ fflush(MR_mdb_out);
+ MR_edt_progress_last_tick = 1;
+ } else if ((MR_edt_start_time
+ + (MR_edt_progress_last_tick + 1)
+ * MR_DECL_DISPLAY_PROGRESS_DELAY)
+ < MR_get_user_cpu_miliseconds())
+ {
+ MR_edt_progress_last_tick++;
+ fprintf(MR_mdb_out,
+ MR_DECL_PROGRESS_TICK_STRING);
+ fflush(MR_mdb_out);
+ }
}
}
}
+static void
+MR_trace_finish_progress() {
+ fprintf(MR_mdb_out, "\n");
+ fflush(MR_mdb_out);
+ MR_edt_progress_last_tick = 0;
+}
+
#ifdef MR_DEBUG_DD_BACK_END
static void
only in patch2:
--- browser/declarative_edt.m 10 May 2005 04:28:21 -0000 1.8
+++ browser/declarative_edt.m 16 May 2005 12:24:02 -0000
@@ -197,7 +197,10 @@
% The origin could not be found due to missing
% information.
- ; not_found.
+ ; not_found
+
+ % An explicit subtree is required.
+ ; require_explicit_subtree.
% The type of primitive operation that bound a subterm that was being
% tracked.
@@ -1004,6 +1007,9 @@
;
Response = require_explicit_subtree
)
+ ;
+ Origin = require_explicit_subtree,
+ Response = require_explicit_subtree
).
% Returns the suspect id in the given list that refers to the given edt
Here's the diff of the CVS log:
--- CVSLOG.old 2005-05-19 20:35:57.000000000 +1000
+++ CVSLOG 2005-05-19 20:40:05.000000000 +1000
@@ -31,6 +31,10 @@
browser/declarative_debugger.m:
Pass the ideal depth of a subtree to the backend.
+browser/declarative_edt.m:
+ Handle the case where edt_dependency says an explicit subtree is
+ required.
+
browser/declarative_execution.m:
Record the ideal depth at the CALL event corresponding to the root
of an implicit subtree.
@@ -41,6 +45,12 @@
Export a new predicate, trace_implicit_tree_info, which is used to
get the info stored at the root of an implicit root.
+ Make trace_dependency respond that an explicit subtree is required
+ if it needs to explore the children of an implicit subtree. Previously
+ we made this situation impossible by requiring the backend to
+ always generate the children of nodes at the depth limit. This,
+ however, complicated the backend code unnecessarily.
+
doc/user_guide.texi:
Change the --depth-step-size dd option to just --depth which is now
only used as the initial depth to build the subtree to. Comment out
@@ -76,6 +86,9 @@
instead of using the value of the global MR_edt_depth_step_size
(which no longer exists).
+ Do not materialize the children of nodes at the depth limit, since
+ this is no longer necessary.
+
trace/mercury_trace_internal.c:
Add and handle the --nodes dd option. Rename the --depth-step-size
option to --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