[m-rev.] for review: fix mantis bug 544

[Julien Fischer]

Hi Zoltan,

Once this is committed, I'll set up a machine to bootcheck the trunk
in a bunch of hlc grades; provided that all passes I will merge it on to
the release branch -- the map fix will go on to the release branch
regardless.

On Mon, 7 Feb 2022, Zoltan Somogyi wrote:

> For review by Julien.
>
> As mentioned in a comment, we could eliminate one source
> of overhead added by this diff by adding a common_subset
> predicate to assoc_list.m. Would anyone object to this?

No objections; ideally map.m and assoc_list.map should support the same
(or at least a very similar) set of operations, both being map ADTs.

> Handle const_var_maps left by add_trail_ops.m.
> 
> This fixes Mantis bug #544.
> 
> The code of add_trail_ops.m can transform
>
>     <code that adds an entry to const_var_map>
> 
> into
>
>     (
>         ...
>         <code that adds an entry to const_var_map>
>         ...
>     ;
>         ...,
>         fail
>     )
> 
> where the const_var_map in the MLDS code generator records which variables'
> values are available as ground terms.
> 
> The MLDS code generator used to reset the const_var_map in its main data
> structure, the ml_gen_info, at the end of every disjunction (actually,
> at the end of every branched control structure) to the value it had
> at the start. This was intended to prevent the code following the branched
> structure from relying on const_var_map entries that were added to the
> const_var_map on *some* branches, but not others. However, in this case,
> it has the effect of forgetting the entry added by the first disjunct,
> even though
> 
> - the code after the disjunction can be reached *only* via the first disjunct,
>   and
> 
> - the code after the disjunction (legitimately, until add_trail_ops) depended
>   on that entry being available.
> 
> The fix is to allow the code after a branched control structure to depend
> on any const_var_map entry that is present in the final const_var_map
> in every branch of the branched control structure whose end is reachable.
> 
> The LLDS code generator was not affected by the bug, because it uses
> a totally separate system for keeping track of what variables' values
> are available statically. In particular, it does not rely on annotations
> left on unifications by the mark_static_term.m pass, having been written
> long before that module existed.

That's one reason the LLDS code generator is not affected; the other is
simply that it introduces trail operations directly and does not use
add_trail_ops.m.

...

> diff --git a/compiler/ml_code_gen.m b/compiler/ml_code_gen.m
> index d70c641be..7d9080d32 100644
> --- a/compiler/ml_code_gen.m
> +++ b/compiler/ml_code_gen.m
> @@ -436,17 +436,32 @@
>      ml_gen_info::in, ml_gen_info::out) is det.
>
>      % Generate code for a goal that is one branch of a branched control
> -    % structure. At the end of the branch, we need to forget what we learned
> +    % structure. At the end of the branch, we forget what we learned
>      % during the branch about which variables are bound to constants,
> -    % since those variables may not be bound to constants (at least not the
> -    % same constants) in parallel branches, or in code after the branched
> -    % control if control did not go through this branch.
> +    % in order to set up for generating code for other branches,
> +    % which should not have access to variable values bounds in earlier
> +    % branches. We do add the final const_var_map to the list of const_var_maps
> +    % if the end of the goal is actually reachable. Our callers should
> +    % thread this list through all the calls that generate code for all the
> +    % branches, and should then give the final list of const_var_maps to
> +    % ml_gen_record_consensus_const_var_map below to compute the const_var_map
> +    % that is appopriate for the program point immediately after the branched

s/appopriate/appropriate/

...


> diff --git a/library/map.m b/library/map.m
> index b5dd93d9c..955c3d4d5 100644
> --- a/library/map.m
> +++ b/library/map.m
> @@ -466,11 +466,11 @@
>
>  %---------------------%
> 
> -    % Given two maps M1 and M2, create a third map M3 that has only the
> -    % keys that occur in both M1 and M2. For keys that occur in both M1
> -    % and M2, compute the corresponding values. If they are the same,
> -    % include the key/value pair in M3. If they differ, do not include the
> -    % key in M3.
> +    % Given two maps MapA and Map3, create a third map CommonMap that

Typo: s/Map3/MapB/

> +    % has only the keys that occur in both MapA and MapB. For keys
> +    % that occur in both MapA and MapB, look up the corresponding values.
> +    % If they are the same, include the key/value pair in CommonMap.
> +    % If they differ, do not include the key in CommonMap.
>      %
>      % This predicate effectively considers the input maps to be sets of
>      % key/value pairs, computes the intersection of those two sets, and
> @@ -482,10 +482,10 @@
>      %
>  :- func common_subset(map(K, V), map(K, V)) = map(K, V).
> 
> -    % Given two maps M1 and M2, create a third map M3 that has only the
> -    % keys that occur in both M1 and M2. For keys that occur in both M1
> -    % and M2, compute the value in the final map by applying the supplied
> -    % predicate to the values associated with the key in M1 and M2.
> +    % Given two maps MapA and MapB, create a third map IntersectMap that has only the
> +    % keys that occur in both MapA and MapB. For keys that occur in both MapA
> +    % and MapB, compute the value in the final map by applying the supplied
> +    % predicate to the values associated with the key in MapA and MapB.
>      % Fail if and only if this predicate fails on the values associated
>      % with some common key.
>      %
> @@ -516,10 +516,11 @@
>
>  %---------------------%
> 
> -    % Given two maps M1 and M2, create a third map M3 that contains all
> -    % the keys that occur in either M1 and M2. For keys that occur in both M1
> -    % and M2, compute the value in the final map by applying the supplied
> -    % closure to the values associated with the key in M1 and M2.
> +    % Given two maps MapA and MapB, create a third map IntersectMap that contains all
> +    % the keys that occur in either MapA and MapB. For keys that occur in both
> +    % MapA
> +    % and MapB, compute the value in the final map by applying the supplied

Formatting.

> +    % closure to the values associated with the key in MapA and MapB.
>      % Fail if and only if this closure fails on the values associated
>      % with some common key.


More generally, I would note that there does not seem to be anything in the test
suite that exercises common_subset.

...

> diff --git a/trace/mercury_trace_cmd_browsing.c b/trace/mercury_trace_cmd_browsing.c
> index 93ab36475..5a39216a6 100644
> --- a/trace/mercury_trace_cmd_browsing.c
> +++ b/trace/mercury_trace_cmd_browsing.c
> @@ -847,6 +847,7 @@ MR_trace_cmd_dump(char **words, int word_count, MR_TraceCmdInfo *cmd,
>              const char  *name;
>
>              MR_convert_arg_to_var_spec(words[1], &var_spec);
> +            // MR_trace_parse_var_path
>              problem = MR_lookup_unambiguous_var_spec(var_spec,
>                  &type_info, &value, &name);
>              if (problem == NULL) {

Did you mean to add this?

The rest looks fine -- thanks for looking into that.

Julien.