[m-rev.] for review: Define equality for version_hash_tables

[Peter Wang]

On Mon, 27 May 2013 10:45:40 +1000, Paul Bone <paul at bone.id.au> wrote:
> For review by anyone.
> 
> Define equality for version_hash_tables.
> 
> library/version_hash_table.m:
>     Add user-defined equality to the version_hash_table/2 type.
> 
>     Use a notag type to make deconstructions easier.
> 
>     Introduce a new function to handle deconstructions that promise that all
>     theoretical solutions are equivilent.

equivalent

> 
>     Rename fields of the inner structure as the num_occupants function
>     no-longer has the same type as the function generated by the field of
>     the same name.
> ---
>  library/version_hash_table.m | 126 ++++++++++++++++++++++++++++++++++---------
>  1 file changed, 102 insertions(+), 24 deletions(-)
> 
> diff --git a/library/version_hash_table.m b/library/version_hash_table.m
> index 04d3389..3640ca5 100644
> --- a/library/version_hash_table.m
> +++ b/library/version_hash_table.m
> @@ -226,17 +226,22 @@
>  :- import_module require.
>  :- import_module string.
>  :- import_module type_desc.
> +:- import_module unit.
>  :- import_module univ.
>  :- import_module version_array.
>  
>  %-----------------------------------------------------------------------------%
>  
>  :- type version_hash_table(K, V)
> +    --->    ht_outer(ht_inner(K, V))
> +    where equality is version_hash_table_equals.
> +
> +:- type ht_inner(K, V)
>      --->    ht(
> -                num_occupants           :: int,
> -                max_occupants           :: int,
> -                hash_pred               :: hash_pred(K),
> -                buckets                 :: buckets(K, V)
> +                ht_num_occupants        :: int,
> +                ht_max_occupants        :: int,
> +                ht_hash_pred            :: hash_pred(K),
> +                ht_buckets              :: buckets(K, V)
>              ).
>  
>  :- type buckets(K, V) == version_array(hash_table_alist(K, V)).
> @@ -282,7 +287,7 @@ init_2(HashPred, N, MaxOccupancy, NeedSafety) = HT :-
>                  NeedSafety = no,
>                  Buckets = version_array.unsafe_new(NumBuckets, ht_nil)
>              ),
> -            HT = ht(0, MaxOccupants, HashPred, Buckets)
> +            HT = ht_outer(ht(0, MaxOccupants, HashPred, Buckets))
>      ).
>  
>  %-----------------------------------------------------------------------------%
> @@ -297,7 +302,9 @@ unsafe_new_default(HashPred) = unsafe_init(HashPred, 7, 0.9).
>  
>  %-----------------------------------------------------------------------------%
>  
> -num_buckets(HT) = size(HT ^ buckets).
> +num_buckets(HT) = size(inner(HT) ^ ht_buckets).
> +
> +num_occupants(HT) = inner(HT) ^ ht_num_occupants.
>  

I think the changes would be cleaner by (un)wrapping within the heads
only, e.g.

    num_occupants(wrap(HT)) = HT ^ ht_num_occupants.

    copy(wrap(HT0)) = wrap(HT) :- ...

where

    :- func wrap(ht_inner(K, V)) = version_hash_table(K, V).
    :- mode wrap(out) = in is det.
    :- mode wrap(in) = out is det.

Also, I would like to see any differences with hash_table.m minimised.

> +:- pred version_hash_table_equals(version_hash_table(K, V)::in,
> +    version_hash_table(K, V)::in) is semidet.

You could name it "version_hash_table.equals".

> +% This pragma is required becase termination analysis can't analyse the use
> +% of higher order code.
> +:- pragma terminates(version_hash_table_equals/2).

because

> +version_hash_table_equals(A, B) :-
> +    promise_pure
> +    ( semipure pointer_equals(A, B) ->
> +        true
> +    ;
> +        inner(A) ^ ht_num_occupants = inner(B) ^ ht_num_occupants,
> +        % XXX: Max occupants is allowed to differ and hash pred may not be
> +        % compared.
> +        fold(compare_item(B), A, unit, _)
> +    ).

Please write out the deconstructions so it's easy to tell which fields
are ignored.  Delete the remark about the max occupants.

> +
> +:- pred compare_item(version_hash_table(K, V)::in, K::in, V::in,
> +    unit::in, unit::out) is semidet.
> +
> +compare_item(Table, K, V, unit, unit) :-
> +    search(Table, K, V).
> +
> +    % We create inner (and the extra level of types) in order to make user
> +    % defined equality easier to support.
> +    %
> +:- pred inner(version_hash_table(K, V)::in, ht_inner(K, V)::out) is det.
> +
> +inner(Outer, Inner) :-
> +    promise_equivalent_solutions [Inner]
> +        Outer = ht_outer(Inner).

Add brackets around the sub-goal.

> +:- func inner(version_hash_table(K, V)) = ht_inner(K, V).
> +:- pragma inline(inner/1).
> +
> +inner(Outer) = Inner :-
> +    inner(Outer, Inner).

Not sure why the extra predicate is necessary.

> +:- semipure pred pointer_equals(T::in, T::in) is semidet.
> +:- pragma inline(pointer_equals/2).
> +
> +:- pragma foreign_proc("C", pointer_equals(A::in, B::in),
> +    [promise_semipure, thread_safe, will_not_call_mercury,
> +        will_not_throw_exception, terminates],
> +    "
> +        SUCCESS_INDICATOR = A == B;
> +    ").

Use standard indentation. Add brackets around the expression.

> +:- pragma foreign_proc("Java", pointer_equals(A::in, B::in),
> +    [promise_semipure, thread_safe, will_not_call_mercury,
> +        will_not_throw_exception, terminates],
> +    "
> +        SUCCESS_INDICATOR = A == B;
> +    ").
> +
> +:- pragma foreign_proc("C#", pointer_equals(A::in, B::in),
> +    [promise_semipure, thread_safe, will_not_call_mercury,
> +        will_not_throw_exception, terminates],
> +    "
> +        SUCCESS_INDICATOR = System.Object.ReferenceEquals(A, B);
> +    ").
> +
> +% Conservative default if a backend does not have pointer equality, such as
> +% Erlang.  (Erlang does have erts_debug:same/1 but I don't know if we can
> +% rely on that.)
> +pointer_equals(A, B) :- false.

Unused variables.  Maybe you need semidet_fail?

Peter