[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