[m-rev.] diff: Avoid goal_path.m conflict.
Paul Bone
pbone at csse.unimelb.edu.au
Fri Jan 14 15:10:08 AEDT 2011
mmake uses VPATH to find sources when compiling Mercury, sources referred to by
dependency files are not path-qualified and therefore compiler/goal_path.m and
mdbcomp/goal_path.m where in conflict. This change renames goal_path.m in
mdbcomp/ to mdbcomp.goal_path.m to avoid this problem.
mdbcomp/goal_path.m:
mdbcomp/mdbcomp.goal_path.m:
As above.
slice/Mmakefile:
deep_profiler/MMakefile:
Conform to the above change.
Index: deep_profiler/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/Mmakefile,v
retrieving revision 1.37
diff -u -p -b -r1.37 Mmakefile
--- deep_profiler/Mmakefile 13 Jan 2011 00:36:55 -0000 1.37
+++ deep_profiler/Mmakefile 14 Jan 2011 04:02:27 -0000
@@ -60,8 +60,8 @@ VPATH = $(LIBRARY_DIR) $(SSDB_DIR)
MDBCOMP_MODULES = \
feedback.automatic_parallelism.m \
feedback.m \
- goal_path.m \
mdbcomp.m \
+ mdbcomp.goal_path.m \
prim_data.m \
program_representation.m \
rtti_access.m \
Index: mdbcomp/goal_path.m
===================================================================
RCS file: mdbcomp/goal_path.m
diff -N mdbcomp/goal_path.m
--- mdbcomp/goal_path.m 13 Jan 2011 00:36:56 -0000 1.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,527 +0,0 @@
-%-----------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et
-%-----------------------------------------------------------------------------%
-% Copyright (C) 2011 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.
-%-----------------------------------------------------------------------------%
-%
-% File: goal_path.m
-% Authors: zs, pbone
-%
-% This module defines the representation of goal paths and goal ids.
-% These identify locations within a procedure body.
-%
-% We can think of the goal that defines a procedure to be a tree, whose leaves
-% are primitive goals and whose interior nodes are compound goals. The goal_id,
-% forward_goal_path and reverse_goal_path types describe the position of a goal
-% in this tree. Therefore value of three types can uniquely identify a goal
-% within its defining procedure.
-%
-% Goal ids are allocated in a depth-first manner that guarantees the following
-% invariants:
-%
-% - the goal id of a goal representing the procedure body will be 0, and
-% - the goal id of a goal will be greater than the goal ids of all the goals
-% that contain it.
-%
-% A goal_path_step type says which branch to take at an interior node;
-% the integer counts inside steps start at one. For switches, the second int,
-% if present, gives the total number of function symbols in the type of the
-% switched-on var. For builtin types such as integer and string, for which
-% this number is effectively infinite, the second number won't be present.
-%
-% A forward goal path lists the step from the root of the tree to the goal
-% being identified.
-%
-% A reverse goal path lists the step from to the goal being identified to
-% the root of the tree.
-%
-% The code in the compiler that allocates goal ids also returns a containing
-% goal map, which maps each goal id to the id of its innermost containing goal
-% (if there is one). When possible, new code should use this data structure,
-% though code that needs to identify goals in files outside the compiler
-% will probably continue to need to use goal paths. The string representations
-% of goal paths always list the steps in the forward order, even though
-% most operations inside the compiler use reverse goal paths, because most
-% operations on goal paths focus on the last element, not the first.
-%
-%-----------------------------------------------------------------------------%
-
-:- module mdbcomp.goal_path.
-:- interface.
-
-:- import_module bimap.
-:- import_module char.
-:- import_module list.
-:- import_module map.
-:- import_module maybe.
-
-%-----------------------------------------------------------------------------%
-
-:- type goal_id
- ---> goal_id(int).
-
-:- type forward_goal_path
- ---> fgp(list(goal_path_step)).
-
-:- type reverse_goal_path
- ---> rgp(list(goal_path_step)).
-
-:- type goal_path_string == string.
-
-:- type goal_path_step
- ---> step_conj(int)
- ; step_disj(int)
- ; step_switch(int, maybe(int))
- ; step_ite_cond
- ; step_ite_then
- ; step_ite_else
- ; step_neg
- ; step_scope(maybe_cut)
- ; step_lambda
- ; step_try
- ; step_atomic_main
- ; step_atomic_orelse(int).
-
- % Does the scope goal have a different determinism inside than outside?
-:- type maybe_cut
- ---> scope_is_cut
- ; scope_is_no_cut.
-
-:- func whole_body_goal_id = goal_id.
-
- % Append a goal path step onto the end of a goal path.
- %
-:- func goal_path_add_at_end(forward_goal_path, goal_path_step) =
- forward_goal_path.
-
- % Append a goal path step onto the end of a reverse goal path.
- %
-:- func rev_goal_path_add_at_end(reverse_goal_path, goal_path_step) =
- reverse_goal_path.
-
- % Remove the last item from the goal path, returning it and the new
- % goal path.
- %
-:- pred goal_path_remove_last(forward_goal_path::in, forward_goal_path::out,
- goal_path_step::out) is semidet.
-
- % Get the last item from the goal path. This fails if the goal path is
- % empty.
- %
-:- pred goal_path_get_last(forward_goal_path::in, goal_path_step::out)
- is semidet.
-
- % Remove the last item from the goal path, returning it and the new
- % goal path.
- %
-:- pred rev_goal_path_remove_last(reverse_goal_path::in,
- reverse_goal_path::out, goal_path_step::out) is semidet.
-
- % Get the last item from the goal path. This fails if the goal path is
- % empty.
- %
-:- pred rev_goal_path_get_last(reverse_goal_path::in, goal_path_step::out)
- is semidet.
-
- % Converts a string to a forward goal path, failing if the string
- % is not a valid goal path.
- %
-:- pred goal_path_from_string(string::in, forward_goal_path::out) is semidet.
-
- % Converts a string to a forward goal path, aborting if the string
- % is not a valid goal path.
- %
-:- pred goal_path_from_string_det(string::in, forward_goal_path::out) is det.
-
- % Converts a string to a reverse goal path, failing if the string
- % is not a valid goal path.
- %
-:- pred rev_goal_path_from_string(string::in, reverse_goal_path::out)
- is semidet.
-
- % Converts a string to a reverse goal path, aborting if the string
- % is not a valid goal path.
- %
-:- pred rev_goal_path_from_string_det(string::in, reverse_goal_path::out)
- is det.
-
- % Converts a string to a goal path step, failing if the string is not
- % a valid goal path step.
- %
-:- pred goal_path_step_from_string(string::in, goal_path_step::out) is semidet.
-
- % Convert the goal path to its string representation. The resulting string
- % is guaranteed to be acceptable to path_from_string_det.
- %
-:- func goal_path_to_string(forward_goal_path) = string.
-
- % Convert the goal path to its string representation. The resulting string
- % is guaranteed to be acceptable to rev_path_from_string_det.
- %
-:- func rev_goal_path_to_string(reverse_goal_path) = string.
-
- % Is this character the one that ends each goal path step?
- %
-:- pred is_goal_path_separator(char::in) is semidet.
-
- % goal_path_inside(PathA, PathB):
- %
- % Succeed if PathB denotes a goal *inside* the goal denoted by PathA.
- % (It considers a goal to be inside itself.)
- %
-:- pred goal_path_inside(forward_goal_path::in, forward_goal_path::in)
- is semidet.
-:- pred rev_goal_path_inside(reverse_goal_path::in, reverse_goal_path::in)
- is semidet.
-
- % goal_path_inside(PathA, PathB, RelativePath):
- %
- % As above, except that it also return RelativePath, which denotes
- % the same goal that PathB denotes, only from GoalA's perspective.
- %
-:- pred goal_path_inside(forward_goal_path::in, forward_goal_path::in,
- forward_goal_path::out) is semidet.
-:- pred rev_goal_path_inside(reverse_goal_path::in, reverse_goal_path::in,
- reverse_goal_path::out) is semidet.
-
- % Remove information from the goal path that depends on type information.
- %
- % This is necessary when using goal paths to lookup a map within the deep
- % profiler. The goal paths used to perform the query cannot construct the
- % parts of the goal paths that depend on type information.
- %
-:- pred rev_goal_path_remove_type_info(reverse_goal_path::in,
- reverse_goal_path::out) is det.
-
-%----------------------------------------------------------------------------%
-
-:- type containing_goal
- ---> whole_body_goal
- % This goal is the entire body of its procedure.
- ; containing_goal(goal_id, goal_path_step).
- % This goal is an contained immediately inside the larger goal
- % identified by the goal_id, from which you need to take the
- % given goal_path step to get to this goal.
- %
- % The goal_id of the containing goal is guaranteed to be always
- % less than the goal_id of this goal.
-
-:- type containing_goal_map == map(goal_id, containing_goal).
-:- type goal_forward_path_map == map(goal_id, forward_goal_path).
-:- type goal_reverse_path_map == map(goal_id, reverse_goal_path).
-:- type goal_reverse_path_bimap == bimap(goal_id, reverse_goal_path).
-
- % goal_id_inside(ContainingGoalMap, GoalIdA, GoalIdB):
- %
- % Succeeds if GoalIdB denotes a goal *inside* the goal denoted by GoalIdA.
- % (It considers a goal to be inside itself.)
- %
-:- pred goal_id_inside(containing_goal_map::in,
- goal_id::in, goal_id::in) is semidet.
-
- % Convert a goal_id to a forward goal path.
- %
-:- func goal_id_to_forward_path(containing_goal_map, goal_id) =
- forward_goal_path.
-
- % Convert a goal_id to a reverse goal path.
- %
-:- func goal_id_to_reverse_path(containing_goal_map, goal_id) =
- reverse_goal_path.
-
- % Given a containing_goal_map, create a map that maps each goal_id in it
- % to a forwward goal path.
- %
-:- func create_forward_goal_path_map(containing_goal_map) =
- goal_forward_path_map.
-
- % Given a containing_goal_map, create a map that maps each goal_id in it
- % to a reverse goal path.
- %
-:- func create_reverse_goal_path_map(containing_goal_map) =
- goal_reverse_path_map.
-
- % Given a containing_goal_map, create a map that maps each goal_id in it
- % to a reverse goal path, and back.
- %
-:- func create_reverse_goal_path_bimap(containing_goal_map) =
- goal_reverse_path_bimap.
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-
-:- implementation.
-
-:- import_module assoc_list.
-:- import_module cord.
-:- import_module pair.
-:- import_module require.
-:- import_module string.
-:- import_module svbimap.
-:- import_module svmap.
-
-whole_body_goal_id = goal_id(0).
-
-goal_path_add_at_end(GoalPath0, GoalPathStep) = GoalPath :-
- GoalPath0 = fgp(Steps0),
- Steps = Steps0 ++ [GoalPathStep],
- GoalPath = fgp(Steps).
-
-rev_goal_path_add_at_end(GoalPath0, GoalPathStep) = GoalPath :-
- GoalPath0 = rgp(Steps0),
- Steps = [GoalPathStep | Steps0],
- GoalPath = rgp(Steps).
-
-goal_path_remove_last(GoalPath0, GoalPath, LastStep) :-
- GoalPath0 = fgp(Steps0),
- list.split_last(Steps0, Steps, LastStep),
- GoalPath = fgp(Steps).
-
-goal_path_get_last(GoalPath, LastStep) :-
- goal_path_remove_last(GoalPath, _, LastStep).
-
-rev_goal_path_remove_last(GoalPath0, GoalPath, LastStep) :-
- GoalPath0 = rgp(Steps0),
- Steps0 = [LastStep | Steps],
- GoalPath = rgp(Steps).
-
-rev_goal_path_get_last(GoalPath, LastStep) :-
- rev_goal_path_remove_last(GoalPath, _, LastStep).
-
-goal_path_inside(PathA, PathB, RelativePath) :-
- PathA = fgp(StepsA),
- PathB = fgp(StepsB),
- list.append(StepsA, RelativeSteps, StepsB),
- RelativePath = fgp(RelativeSteps).
-
-rev_goal_path_inside(PathA, PathB, Relative) :-
- PathA = rgp(StepsA),
- PathB = rgp(StepsB),
- list.remove_suffix(StepsB, StepsA, RelativeSteps),
- Relative = rgp(RelativeSteps).
-
-goal_path_inside(PathA, PathB) :-
- goal_path_inside(PathA, PathB, _).
-
-rev_goal_path_inside(PathA, PathB) :-
- rev_goal_path_inside(PathA, PathB, _).
-
-goal_path_from_string(GoalPathStr, GoalPath) :-
- StepStrs = string.words_separator(is_goal_path_separator, GoalPathStr),
- list.map(goal_path_step_from_string, StepStrs, Steps),
- GoalPath = fgp(Steps).
-
-goal_path_from_string_det(GoalPathStr, GoalPath) :-
- ( goal_path_from_string(GoalPathStr, GoalPathPrime) ->
- GoalPath = GoalPathPrime
- ;
- unexpected($module, $pred, "goal_path_from_string failed")
- ).
-
-rev_goal_path_from_string(GoalPathStr, GoalPath) :-
- StepStrs = string.words_separator(is_goal_path_separator, GoalPathStr),
- list.map(goal_path_step_from_string, StepStrs, Steps),
- list.reverse(Steps, RevSteps),
- GoalPath = rgp(RevSteps).
-
-rev_goal_path_from_string_det(GoalPathStr, GoalPath) :-
- ( rev_goal_path_from_string(GoalPathStr, GoalPathPrime) ->
- GoalPath = GoalPathPrime
- ;
- unexpected($module, $pred, "rev_goal_path_from_string failed")
- ).
-
-goal_path_step_from_string(String, Step) :-
- string.first_char(String, First, Rest),
- goal_path_step_from_string_2(First, Rest, Step).
-
-:- pred goal_path_step_from_string_2(char::in, string::in, goal_path_step::out)
- is semidet.
-
-goal_path_step_from_string_2('c', NStr, step_conj(N)) :-
- string.to_int(NStr, N).
-goal_path_step_from_string_2('d', NStr, step_disj(N)) :-
- string.to_int(NStr, N).
-goal_path_step_from_string_2('s', Str, step_switch(N, MaybeM)) :-
- string.words_separator(unify('-'), Str) = [NStr, MStr],
- string.to_int(NStr, N),
- % "na" is short for "not applicable"
- ( MStr = "na" ->
- MaybeM = no
- ;
- string.to_int(MStr, M),
- MaybeM = yes(M)
- ).
-goal_path_step_from_string_2('?', "", step_ite_cond).
-goal_path_step_from_string_2('t', "", step_ite_then).
-goal_path_step_from_string_2('e', "", step_ite_else).
-goal_path_step_from_string_2('~', "", step_neg).
-goal_path_step_from_string_2('q', "!", step_scope(scope_is_cut)).
-goal_path_step_from_string_2('q', "", step_scope(scope_is_no_cut)).
-goal_path_step_from_string_2('r', "", step_try).
-goal_path_step_from_string_2('=', "", step_lambda).
-goal_path_step_from_string_2('a', "", step_atomic_main).
-goal_path_step_from_string_2('o', NStr, step_atomic_orelse(N)) :-
- string.to_int(NStr, N).
-
-is_goal_path_separator(';').
-
-goal_path_to_string(GoalPath) = GoalPathStr :-
- GoalPath = fgp(Steps),
- StepStrs = list.map(goal_path_step_to_string, Steps),
- string.append_list(StepStrs, GoalPathStr).
-
-rev_goal_path_to_string(GoalPath) = GoalPathStr :-
- GoalPath = rgp(RevSteps),
- list.reverse(RevSteps, Steps),
- StepStrs = list.map(goal_path_step_to_string, Steps),
- string.append_list(StepStrs, GoalPathStr).
-
-:- func goal_path_step_to_string(goal_path_step) = string.
-
-goal_path_step_to_string(step_conj(N)) = "c" ++ int_to_string(N) ++ ";".
-goal_path_step_to_string(step_disj(N)) = "d" ++ int_to_string(N) ++ ";".
-goal_path_step_to_string(step_switch(N, yes(M))) = "s" ++ int_to_string(N)
- ++ "-" ++ int_to_string(M) ++ ";".
-goal_path_step_to_string(step_switch(N, no)) = "s" ++ int_to_string(N)
- ++ "-na;". % short for "not applicable"
-goal_path_step_to_string(step_ite_cond) = "?;".
-goal_path_step_to_string(step_ite_then) = "t;".
-goal_path_step_to_string(step_ite_else) = "e;".
-goal_path_step_to_string(step_neg) = "~;".
-goal_path_step_to_string(step_scope(scope_is_cut)) = "q!;".
-goal_path_step_to_string(step_scope(scope_is_no_cut)) = "q;".
-goal_path_step_to_string(step_try) = "r;".
-goal_path_step_to_string(step_lambda) = "=;".
-goal_path_step_to_string(step_atomic_main) = "a;".
-goal_path_step_to_string(step_atomic_orelse(N)) =
- "o" ++ int_to_string(N) ++ ";".
-
-rev_goal_path_remove_type_info(rgp(Steps0), rgp(Steps)) :-
- map(goal_path_step_remove_type_info, Steps0, Steps).
-
-:- pred goal_path_step_remove_type_info(goal_path_step::in,
- goal_path_step::out) is det.
-
-goal_path_step_remove_type_info(!Step) :-
- (
- ( !.Step = step_conj(_)
- ; !.Step = step_disj(_)
- ; !.Step = step_ite_cond
- ; !.Step = step_ite_then
- ; !.Step = step_ite_else
- ; !.Step = step_neg
- ; !.Step = step_scope(_)
- ; !.Step = step_lambda
- ; !.Step = step_try
- ; !.Step = step_atomic_main
- ; !.Step = step_atomic_orelse(_)
- )
- ;
- !.Step = step_switch(N, _),
- !:Step = step_switch(N, no)
- ).
-
-%-----------------------------------------------------------------------------%
-
-goal_id_inside(ContainingGoalId, GoalIdA, GoalIdB) :-
- (
- GoalIdB = GoalIdA
- ;
- map.lookup(ContainingGoalId, GoalIdB, GoalContainingB),
- GoalContainingB = containing_goal(ParentGoalIdB, _),
- goal_id_inside(ContainingGoalId, GoalIdA, ParentGoalIdB)
- ).
-
-goal_id_to_forward_path(ContainingGoalMap, GoalId) = GoalPath :-
- StepsCord = goal_id_to_steps(ContainingGoalMap, GoalId),
- Steps = cord.list(StepsCord),
- GoalPath = fgp(Steps).
-
-goal_id_to_reverse_path(ContainingGoalMap, GoalId) = GoalPath :-
- StepsCord = goal_id_to_steps(ContainingGoalMap, GoalId),
- Steps = cord.list(StepsCord),
- list.reverse(Steps, RevSteps),
- GoalPath = rgp(RevSteps).
-
-:- func goal_id_to_steps(containing_goal_map, goal_id) =
- cord(goal_path_step).
-
-goal_id_to_steps(ContainingGoalMap, GoalId) = Steps :-
- map.lookup(ContainingGoalMap, GoalId, ContainingGoal),
- (
- ContainingGoal = whole_body_goal,
- Steps = cord.empty
- ;
- ContainingGoal = containing_goal(ParentGoalId, LastStep),
- EarlierSteps = goal_id_to_steps(ContainingGoalMap, ParentGoalId),
- Steps = cord.snoc(EarlierSteps, LastStep)
- ).
-
-create_forward_goal_path_map(ContainingGoalMap) = ForwardGoalPathMap :-
- ReverseGoalPathMap = create_reverse_goal_path_map(ContainingGoalMap),
- map.map_values_only(rgp_to_fgp, ReverseGoalPathMap, ForwardGoalPathMap).
-
-:- pred rgp_to_fgp(reverse_goal_path::in, forward_goal_path::out) is det.
-
-rgp_to_fgp(rgp(RevSteps), fgp(Steps)) :-
- list.reverse(RevSteps, Steps).
-
-create_reverse_goal_path_map(ContainingGoalMap) = ReverseGoalPathMap :-
- map.to_assoc_list(ContainingGoalMap, ContainingGoalList),
- create_reverse_goal_path_map_2(ContainingGoalList,
- map.init, ReverseGoalPathMap).
-
-:- pred create_reverse_goal_path_map_2(
- assoc_list(goal_id, containing_goal)::in,
- map(goal_id, reverse_goal_path)::in, map(goal_id, reverse_goal_path)::out)
- is det.
-
-create_reverse_goal_path_map_2([], !ReverseGoalPathMap).
-create_reverse_goal_path_map_2([Head | Tail], !ReverseGoalPathMap) :-
- Head = GoalId - ContainingGoal,
- (
- ContainingGoal = whole_body_goal,
- GoalReversePath = rgp([])
- ;
- ContainingGoal = containing_goal(ContainingGoalId, Step),
- map.lookup(!.ReverseGoalPathMap, ContainingGoalId,
- ContainingGoalReversePath),
- ContainingGoalReversePath = rgp(ContainingGoalReverseSteps),
- GoalReverseSteps = [Step | ContainingGoalReverseSteps],
- GoalReversePath = rgp(GoalReverseSteps)
- ),
- svmap.det_insert(GoalId, GoalReversePath, !ReverseGoalPathMap),
- create_reverse_goal_path_map_2(Tail, !ReverseGoalPathMap).
-
-create_reverse_goal_path_bimap(ContainingGoalMap) = ReverseGoalPathBiMap :-
- map.to_assoc_list(ContainingGoalMap, ContainingGoalList),
- create_reverse_goal_path_bimap_2(ContainingGoalList,
- bimap.init, ReverseGoalPathBiMap).
-
-:- pred create_reverse_goal_path_bimap_2(
- assoc_list(goal_id, containing_goal)::in,
- bimap(goal_id, reverse_goal_path)::in,
- bimap(goal_id, reverse_goal_path)::out) is det.
-
-create_reverse_goal_path_bimap_2([], !ReverseGoalPathBiMap).
-create_reverse_goal_path_bimap_2([Head | Tail], !ReverseGoalPathBiMap) :-
- Head = GoalId - ContainingGoal,
- (
- ContainingGoal = whole_body_goal,
- GoalReversePath = rgp([])
- ;
- ContainingGoal = containing_goal(ContainingGoalId, Step),
- bimap.lookup(!.ReverseGoalPathBiMap, ContainingGoalId,
- ContainingGoalReversePath),
- ContainingGoalReversePath = rgp(ContainingGoalReverseSteps),
- GoalReverseSteps = [Step | ContainingGoalReverseSteps],
- GoalReversePath = rgp(GoalReverseSteps)
- ),
- svbimap.det_insert(GoalId, GoalReversePath, !ReverseGoalPathBiMap),
- create_reverse_goal_path_bimap_2(Tail, !ReverseGoalPathBiMap).
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
Index: mdbcomp/mdbcomp.goal_path.m
===================================================================
RCS file: mdbcomp/mdbcomp.goal_path.m
diff -N mdbcomp/mdbcomp.goal_path.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ mdbcomp/mdbcomp.goal_path.m 14 Jan 2011 04:02:27 -0000
@@ -0,0 +1,527 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2011 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.
+%-----------------------------------------------------------------------------%
+%
+% File: goal_path.m
+% Authors: zs, pbone
+%
+% This module defines the representation of goal paths and goal ids.
+% These identify locations within a procedure body.
+%
+% We can think of the goal that defines a procedure to be a tree, whose leaves
+% are primitive goals and whose interior nodes are compound goals. The goal_id,
+% forward_goal_path and reverse_goal_path types describe the position of a goal
+% in this tree. Therefore value of three types can uniquely identify a goal
+% within its defining procedure.
+%
+% Goal ids are allocated in a depth-first manner that guarantees the following
+% invariants:
+%
+% - the goal id of a goal representing the procedure body will be 0, and
+% - the goal id of a goal will be greater than the goal ids of all the goals
+% that contain it.
+%
+% A goal_path_step type says which branch to take at an interior node;
+% the integer counts inside steps start at one. For switches, the second int,
+% if present, gives the total number of function symbols in the type of the
+% switched-on var. For builtin types such as integer and string, for which
+% this number is effectively infinite, the second number won't be present.
+%
+% A forward goal path lists the step from the root of the tree to the goal
+% being identified.
+%
+% A reverse goal path lists the step from to the goal being identified to
+% the root of the tree.
+%
+% The code in the compiler that allocates goal ids also returns a containing
+% goal map, which maps each goal id to the id of its innermost containing goal
+% (if there is one). When possible, new code should use this data structure,
+% though code that needs to identify goals in files outside the compiler
+% will probably continue to need to use goal paths. The string representations
+% of goal paths always list the steps in the forward order, even though
+% most operations inside the compiler use reverse goal paths, because most
+% operations on goal paths focus on the last element, not the first.
+%
+%-----------------------------------------------------------------------------%
+
+:- module mdbcomp.goal_path.
+:- interface.
+
+:- import_module bimap.
+:- import_module char.
+:- import_module list.
+:- import_module map.
+:- import_module maybe.
+
+%-----------------------------------------------------------------------------%
+
+:- type goal_id
+ ---> goal_id(int).
+
+:- type forward_goal_path
+ ---> fgp(list(goal_path_step)).
+
+:- type reverse_goal_path
+ ---> rgp(list(goal_path_step)).
+
+:- type goal_path_string == string.
+
+:- type goal_path_step
+ ---> step_conj(int)
+ ; step_disj(int)
+ ; step_switch(int, maybe(int))
+ ; step_ite_cond
+ ; step_ite_then
+ ; step_ite_else
+ ; step_neg
+ ; step_scope(maybe_cut)
+ ; step_lambda
+ ; step_try
+ ; step_atomic_main
+ ; step_atomic_orelse(int).
+
+ % Does the scope goal have a different determinism inside than outside?
+:- type maybe_cut
+ ---> scope_is_cut
+ ; scope_is_no_cut.
+
+:- func whole_body_goal_id = goal_id.
+
+ % Append a goal path step onto the end of a goal path.
+ %
+:- func goal_path_add_at_end(forward_goal_path, goal_path_step) =
+ forward_goal_path.
+
+ % Append a goal path step onto the end of a reverse goal path.
+ %
+:- func rev_goal_path_add_at_end(reverse_goal_path, goal_path_step) =
+ reverse_goal_path.
+
+ % Remove the last item from the goal path, returning it and the new
+ % goal path.
+ %
+:- pred goal_path_remove_last(forward_goal_path::in, forward_goal_path::out,
+ goal_path_step::out) is semidet.
+
+ % Get the last item from the goal path. This fails if the goal path is
+ % empty.
+ %
+:- pred goal_path_get_last(forward_goal_path::in, goal_path_step::out)
+ is semidet.
+
+ % Remove the last item from the goal path, returning it and the new
+ % goal path.
+ %
+:- pred rev_goal_path_remove_last(reverse_goal_path::in,
+ reverse_goal_path::out, goal_path_step::out) is semidet.
+
+ % Get the last item from the goal path. This fails if the goal path is
+ % empty.
+ %
+:- pred rev_goal_path_get_last(reverse_goal_path::in, goal_path_step::out)
+ is semidet.
+
+ % Converts a string to a forward goal path, failing if the string
+ % is not a valid goal path.
+ %
+:- pred goal_path_from_string(string::in, forward_goal_path::out) is semidet.
+
+ % Converts a string to a forward goal path, aborting if the string
+ % is not a valid goal path.
+ %
+:- pred goal_path_from_string_det(string::in, forward_goal_path::out) is det.
+
+ % Converts a string to a reverse goal path, failing if the string
+ % is not a valid goal path.
+ %
+:- pred rev_goal_path_from_string(string::in, reverse_goal_path::out)
+ is semidet.
+
+ % Converts a string to a reverse goal path, aborting if the string
+ % is not a valid goal path.
+ %
+:- pred rev_goal_path_from_string_det(string::in, reverse_goal_path::out)
+ is det.
+
+ % Converts a string to a goal path step, failing if the string is not
+ % a valid goal path step.
+ %
+:- pred goal_path_step_from_string(string::in, goal_path_step::out) is semidet.
+
+ % Convert the goal path to its string representation. The resulting string
+ % is guaranteed to be acceptable to path_from_string_det.
+ %
+:- func goal_path_to_string(forward_goal_path) = string.
+
+ % Convert the goal path to its string representation. The resulting string
+ % is guaranteed to be acceptable to rev_path_from_string_det.
+ %
+:- func rev_goal_path_to_string(reverse_goal_path) = string.
+
+ % Is this character the one that ends each goal path step?
+ %
+:- pred is_goal_path_separator(char::in) is semidet.
+
+ % goal_path_inside(PathA, PathB):
+ %
+ % Succeed if PathB denotes a goal *inside* the goal denoted by PathA.
+ % (It considers a goal to be inside itself.)
+ %
+:- pred goal_path_inside(forward_goal_path::in, forward_goal_path::in)
+ is semidet.
+:- pred rev_goal_path_inside(reverse_goal_path::in, reverse_goal_path::in)
+ is semidet.
+
+ % goal_path_inside(PathA, PathB, RelativePath):
+ %
+ % As above, except that it also return RelativePath, which denotes
+ % the same goal that PathB denotes, only from GoalA's perspective.
+ %
+:- pred goal_path_inside(forward_goal_path::in, forward_goal_path::in,
+ forward_goal_path::out) is semidet.
+:- pred rev_goal_path_inside(reverse_goal_path::in, reverse_goal_path::in,
+ reverse_goal_path::out) is semidet.
+
+ % Remove information from the goal path that depends on type information.
+ %
+ % This is necessary when using goal paths to lookup a map within the deep
+ % profiler. The goal paths used to perform the query cannot construct the
+ % parts of the goal paths that depend on type information.
+ %
+:- pred rev_goal_path_remove_type_info(reverse_goal_path::in,
+ reverse_goal_path::out) is det.
+
+%----------------------------------------------------------------------------%
+
+:- type containing_goal
+ ---> whole_body_goal
+ % This goal is the entire body of its procedure.
+ ; containing_goal(goal_id, goal_path_step).
+ % This goal is an contained immediately inside the larger goal
+ % identified by the goal_id, from which you need to take the
+ % given goal_path step to get to this goal.
+ %
+ % The goal_id of the containing goal is guaranteed to be always
+ % less than the goal_id of this goal.
+
+:- type containing_goal_map == map(goal_id, containing_goal).
+:- type goal_forward_path_map == map(goal_id, forward_goal_path).
+:- type goal_reverse_path_map == map(goal_id, reverse_goal_path).
+:- type goal_reverse_path_bimap == bimap(goal_id, reverse_goal_path).
+
+ % goal_id_inside(ContainingGoalMap, GoalIdA, GoalIdB):
+ %
+ % Succeeds if GoalIdB denotes a goal *inside* the goal denoted by GoalIdA.
+ % (It considers a goal to be inside itself.)
+ %
+:- pred goal_id_inside(containing_goal_map::in,
+ goal_id::in, goal_id::in) is semidet.
+
+ % Convert a goal_id to a forward goal path.
+ %
+:- func goal_id_to_forward_path(containing_goal_map, goal_id) =
+ forward_goal_path.
+
+ % Convert a goal_id to a reverse goal path.
+ %
+:- func goal_id_to_reverse_path(containing_goal_map, goal_id) =
+ reverse_goal_path.
+
+ % Given a containing_goal_map, create a map that maps each goal_id in it
+ % to a forwward goal path.
+ %
+:- func create_forward_goal_path_map(containing_goal_map) =
+ goal_forward_path_map.
+
+ % Given a containing_goal_map, create a map that maps each goal_id in it
+ % to a reverse goal path.
+ %
+:- func create_reverse_goal_path_map(containing_goal_map) =
+ goal_reverse_path_map.
+
+ % Given a containing_goal_map, create a map that maps each goal_id in it
+ % to a reverse goal path, and back.
+ %
+:- func create_reverse_goal_path_bimap(containing_goal_map) =
+ goal_reverse_path_bimap.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module assoc_list.
+:- import_module cord.
+:- import_module pair.
+:- import_module require.
+:- import_module string.
+:- import_module svbimap.
+:- import_module svmap.
+
+whole_body_goal_id = goal_id(0).
+
+goal_path_add_at_end(GoalPath0, GoalPathStep) = GoalPath :-
+ GoalPath0 = fgp(Steps0),
+ Steps = Steps0 ++ [GoalPathStep],
+ GoalPath = fgp(Steps).
+
+rev_goal_path_add_at_end(GoalPath0, GoalPathStep) = GoalPath :-
+ GoalPath0 = rgp(Steps0),
+ Steps = [GoalPathStep | Steps0],
+ GoalPath = rgp(Steps).
+
+goal_path_remove_last(GoalPath0, GoalPath, LastStep) :-
+ GoalPath0 = fgp(Steps0),
+ list.split_last(Steps0, Steps, LastStep),
+ GoalPath = fgp(Steps).
+
+goal_path_get_last(GoalPath, LastStep) :-
+ goal_path_remove_last(GoalPath, _, LastStep).
+
+rev_goal_path_remove_last(GoalPath0, GoalPath, LastStep) :-
+ GoalPath0 = rgp(Steps0),
+ Steps0 = [LastStep | Steps],
+ GoalPath = rgp(Steps).
+
+rev_goal_path_get_last(GoalPath, LastStep) :-
+ rev_goal_path_remove_last(GoalPath, _, LastStep).
+
+goal_path_inside(PathA, PathB, RelativePath) :-
+ PathA = fgp(StepsA),
+ PathB = fgp(StepsB),
+ list.append(StepsA, RelativeSteps, StepsB),
+ RelativePath = fgp(RelativeSteps).
+
+rev_goal_path_inside(PathA, PathB, Relative) :-
+ PathA = rgp(StepsA),
+ PathB = rgp(StepsB),
+ list.remove_suffix(StepsB, StepsA, RelativeSteps),
+ Relative = rgp(RelativeSteps).
+
+goal_path_inside(PathA, PathB) :-
+ goal_path_inside(PathA, PathB, _).
+
+rev_goal_path_inside(PathA, PathB) :-
+ rev_goal_path_inside(PathA, PathB, _).
+
+goal_path_from_string(GoalPathStr, GoalPath) :-
+ StepStrs = string.words_separator(is_goal_path_separator, GoalPathStr),
+ list.map(goal_path_step_from_string, StepStrs, Steps),
+ GoalPath = fgp(Steps).
+
+goal_path_from_string_det(GoalPathStr, GoalPath) :-
+ ( goal_path_from_string(GoalPathStr, GoalPathPrime) ->
+ GoalPath = GoalPathPrime
+ ;
+ unexpected($module, $pred, "goal_path_from_string failed")
+ ).
+
+rev_goal_path_from_string(GoalPathStr, GoalPath) :-
+ StepStrs = string.words_separator(is_goal_path_separator, GoalPathStr),
+ list.map(goal_path_step_from_string, StepStrs, Steps),
+ list.reverse(Steps, RevSteps),
+ GoalPath = rgp(RevSteps).
+
+rev_goal_path_from_string_det(GoalPathStr, GoalPath) :-
+ ( rev_goal_path_from_string(GoalPathStr, GoalPathPrime) ->
+ GoalPath = GoalPathPrime
+ ;
+ unexpected($module, $pred, "rev_goal_path_from_string failed")
+ ).
+
+goal_path_step_from_string(String, Step) :-
+ string.first_char(String, First, Rest),
+ goal_path_step_from_string_2(First, Rest, Step).
+
+:- pred goal_path_step_from_string_2(char::in, string::in, goal_path_step::out)
+ is semidet.
+
+goal_path_step_from_string_2('c', NStr, step_conj(N)) :-
+ string.to_int(NStr, N).
+goal_path_step_from_string_2('d', NStr, step_disj(N)) :-
+ string.to_int(NStr, N).
+goal_path_step_from_string_2('s', Str, step_switch(N, MaybeM)) :-
+ string.words_separator(unify('-'), Str) = [NStr, MStr],
+ string.to_int(NStr, N),
+ % "na" is short for "not applicable"
+ ( MStr = "na" ->
+ MaybeM = no
+ ;
+ string.to_int(MStr, M),
+ MaybeM = yes(M)
+ ).
+goal_path_step_from_string_2('?', "", step_ite_cond).
+goal_path_step_from_string_2('t', "", step_ite_then).
+goal_path_step_from_string_2('e', "", step_ite_else).
+goal_path_step_from_string_2('~', "", step_neg).
+goal_path_step_from_string_2('q', "!", step_scope(scope_is_cut)).
+goal_path_step_from_string_2('q', "", step_scope(scope_is_no_cut)).
+goal_path_step_from_string_2('r', "", step_try).
+goal_path_step_from_string_2('=', "", step_lambda).
+goal_path_step_from_string_2('a', "", step_atomic_main).
+goal_path_step_from_string_2('o', NStr, step_atomic_orelse(N)) :-
+ string.to_int(NStr, N).
+
+is_goal_path_separator(';').
+
+goal_path_to_string(GoalPath) = GoalPathStr :-
+ GoalPath = fgp(Steps),
+ StepStrs = list.map(goal_path_step_to_string, Steps),
+ string.append_list(StepStrs, GoalPathStr).
+
+rev_goal_path_to_string(GoalPath) = GoalPathStr :-
+ GoalPath = rgp(RevSteps),
+ list.reverse(RevSteps, Steps),
+ StepStrs = list.map(goal_path_step_to_string, Steps),
+ string.append_list(StepStrs, GoalPathStr).
+
+:- func goal_path_step_to_string(goal_path_step) = string.
+
+goal_path_step_to_string(step_conj(N)) = "c" ++ int_to_string(N) ++ ";".
+goal_path_step_to_string(step_disj(N)) = "d" ++ int_to_string(N) ++ ";".
+goal_path_step_to_string(step_switch(N, yes(M))) = "s" ++ int_to_string(N)
+ ++ "-" ++ int_to_string(M) ++ ";".
+goal_path_step_to_string(step_switch(N, no)) = "s" ++ int_to_string(N)
+ ++ "-na;". % short for "not applicable"
+goal_path_step_to_string(step_ite_cond) = "?;".
+goal_path_step_to_string(step_ite_then) = "t;".
+goal_path_step_to_string(step_ite_else) = "e;".
+goal_path_step_to_string(step_neg) = "~;".
+goal_path_step_to_string(step_scope(scope_is_cut)) = "q!;".
+goal_path_step_to_string(step_scope(scope_is_no_cut)) = "q;".
+goal_path_step_to_string(step_try) = "r;".
+goal_path_step_to_string(step_lambda) = "=;".
+goal_path_step_to_string(step_atomic_main) = "a;".
+goal_path_step_to_string(step_atomic_orelse(N)) =
+ "o" ++ int_to_string(N) ++ ";".
+
+rev_goal_path_remove_type_info(rgp(Steps0), rgp(Steps)) :-
+ map(goal_path_step_remove_type_info, Steps0, Steps).
+
+:- pred goal_path_step_remove_type_info(goal_path_step::in,
+ goal_path_step::out) is det.
+
+goal_path_step_remove_type_info(!Step) :-
+ (
+ ( !.Step = step_conj(_)
+ ; !.Step = step_disj(_)
+ ; !.Step = step_ite_cond
+ ; !.Step = step_ite_then
+ ; !.Step = step_ite_else
+ ; !.Step = step_neg
+ ; !.Step = step_scope(_)
+ ; !.Step = step_lambda
+ ; !.Step = step_try
+ ; !.Step = step_atomic_main
+ ; !.Step = step_atomic_orelse(_)
+ )
+ ;
+ !.Step = step_switch(N, _),
+ !:Step = step_switch(N, no)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+goal_id_inside(ContainingGoalId, GoalIdA, GoalIdB) :-
+ (
+ GoalIdB = GoalIdA
+ ;
+ map.lookup(ContainingGoalId, GoalIdB, GoalContainingB),
+ GoalContainingB = containing_goal(ParentGoalIdB, _),
+ goal_id_inside(ContainingGoalId, GoalIdA, ParentGoalIdB)
+ ).
+
+goal_id_to_forward_path(ContainingGoalMap, GoalId) = GoalPath :-
+ StepsCord = goal_id_to_steps(ContainingGoalMap, GoalId),
+ Steps = cord.list(StepsCord),
+ GoalPath = fgp(Steps).
+
+goal_id_to_reverse_path(ContainingGoalMap, GoalId) = GoalPath :-
+ StepsCord = goal_id_to_steps(ContainingGoalMap, GoalId),
+ Steps = cord.list(StepsCord),
+ list.reverse(Steps, RevSteps),
+ GoalPath = rgp(RevSteps).
+
+:- func goal_id_to_steps(containing_goal_map, goal_id) =
+ cord(goal_path_step).
+
+goal_id_to_steps(ContainingGoalMap, GoalId) = Steps :-
+ map.lookup(ContainingGoalMap, GoalId, ContainingGoal),
+ (
+ ContainingGoal = whole_body_goal,
+ Steps = cord.empty
+ ;
+ ContainingGoal = containing_goal(ParentGoalId, LastStep),
+ EarlierSteps = goal_id_to_steps(ContainingGoalMap, ParentGoalId),
+ Steps = cord.snoc(EarlierSteps, LastStep)
+ ).
+
+create_forward_goal_path_map(ContainingGoalMap) = ForwardGoalPathMap :-
+ ReverseGoalPathMap = create_reverse_goal_path_map(ContainingGoalMap),
+ map.map_values_only(rgp_to_fgp, ReverseGoalPathMap, ForwardGoalPathMap).
+
+:- pred rgp_to_fgp(reverse_goal_path::in, forward_goal_path::out) is det.
+
+rgp_to_fgp(rgp(RevSteps), fgp(Steps)) :-
+ list.reverse(RevSteps, Steps).
+
+create_reverse_goal_path_map(ContainingGoalMap) = ReverseGoalPathMap :-
+ map.to_assoc_list(ContainingGoalMap, ContainingGoalList),
+ create_reverse_goal_path_map_2(ContainingGoalList,
+ map.init, ReverseGoalPathMap).
+
+:- pred create_reverse_goal_path_map_2(
+ assoc_list(goal_id, containing_goal)::in,
+ map(goal_id, reverse_goal_path)::in, map(goal_id, reverse_goal_path)::out)
+ is det.
+
+create_reverse_goal_path_map_2([], !ReverseGoalPathMap).
+create_reverse_goal_path_map_2([Head | Tail], !ReverseGoalPathMap) :-
+ Head = GoalId - ContainingGoal,
+ (
+ ContainingGoal = whole_body_goal,
+ GoalReversePath = rgp([])
+ ;
+ ContainingGoal = containing_goal(ContainingGoalId, Step),
+ map.lookup(!.ReverseGoalPathMap, ContainingGoalId,
+ ContainingGoalReversePath),
+ ContainingGoalReversePath = rgp(ContainingGoalReverseSteps),
+ GoalReverseSteps = [Step | ContainingGoalReverseSteps],
+ GoalReversePath = rgp(GoalReverseSteps)
+ ),
+ svmap.det_insert(GoalId, GoalReversePath, !ReverseGoalPathMap),
+ create_reverse_goal_path_map_2(Tail, !ReverseGoalPathMap).
+
+create_reverse_goal_path_bimap(ContainingGoalMap) = ReverseGoalPathBiMap :-
+ map.to_assoc_list(ContainingGoalMap, ContainingGoalList),
+ create_reverse_goal_path_bimap_2(ContainingGoalList,
+ bimap.init, ReverseGoalPathBiMap).
+
+:- pred create_reverse_goal_path_bimap_2(
+ assoc_list(goal_id, containing_goal)::in,
+ bimap(goal_id, reverse_goal_path)::in,
+ bimap(goal_id, reverse_goal_path)::out) is det.
+
+create_reverse_goal_path_bimap_2([], !ReverseGoalPathBiMap).
+create_reverse_goal_path_bimap_2([Head | Tail], !ReverseGoalPathBiMap) :-
+ Head = GoalId - ContainingGoal,
+ (
+ ContainingGoal = whole_body_goal,
+ GoalReversePath = rgp([])
+ ;
+ ContainingGoal = containing_goal(ContainingGoalId, Step),
+ bimap.lookup(!.ReverseGoalPathBiMap, ContainingGoalId,
+ ContainingGoalReversePath),
+ ContainingGoalReversePath = rgp(ContainingGoalReverseSteps),
+ GoalReverseSteps = [Step | ContainingGoalReverseSteps],
+ GoalReversePath = rgp(GoalReverseSteps)
+ ),
+ svbimap.det_insert(GoalId, GoalReversePath, !ReverseGoalPathBiMap),
+ create_reverse_goal_path_bimap_2(Tail, !ReverseGoalPathBiMap).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: slice/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/mercury/slice/Mmakefile,v
retrieving revision 1.23
diff -u -p -b -r1.23 Mmakefile
--- slice/Mmakefile 13 Jan 2011 00:36:56 -0000 1.23
+++ slice/Mmakefile 14 Jan 2011 04:02:27 -0000
@@ -49,8 +49,8 @@ VPATH = $(LIBRARY_DIR) $(SSDB_DIR)
MDBCOMP_MODULES = \
feedback.automatic_parallelism.m \
feedback.m \
- goal_path.m \
mdbcomp.m \
+ mdbcomp.goal_path.m \
prim_data.m \
program_representation.m \
rtti_access.m \
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 489 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20110114/9fe736af/attachment.sig>
More information about the reviews
mailing list