[m-dev.] For review: updates to library/rbtree.m

[Warwick Harvey]

Fergus Henderson wrote:
> I hope you can get it working.  If you can't, let us know what
> the failure symptom is.

I've *finally* figured out what the problem is (I wrote a "debug" tree
module which calls both the rbtree and the tree234 modules and compares
the results, aborting if there's a difference, and then traced the
problem back to its source).

It looks like the problem is *not* in the rbtree module.  It looks like
the preconditions for map:merge are being violated in the compiler. 
Specifically:

        % For map__merge(MapA, MapB, Map), MapA and MapB must
        % not both contain the same key.

... and it's being called with two maps with a common key.  The
difference between the two tree implementations is that one inserts
(using `set') the entries in one order, and the other in the reverse,
resulting in different maps.  (Incidentally, rbtree could do with a
*lot* of improvement in its "whole tree" construction/deconstruction
predicates --- what's there is simple, but inefficient unless the
compiler is even smarter than I think it is).

Exhibiting example: compiling declarative_analyser.m in the browser
directory.

Stack trace of exhibiting example:
   1       pred map:merge/3-0 (det) (map.m:426)
   2       pred inlining:do_inline_call/13-0 (det) (inlining.m:631)
   3       pred inlining:inlining_in_goal/4-0 (det) (inlining.m:509)
   4    3* pred inlining:inlining_in_conj/4-0 (det) (inlining.m:715 and
others)
   7    2* pred inlining:inlining_in_goal/4-0 (det) (inlining.m:456 and
others)
   9    2* pred inlining:inlining_in_conj/4-0 (det) (inlining.m:715 and
others)
  11       pred inlining:inlining_in_goal/4-0 (det) (inlining.m:456)
  12       pred inlining:in_predproc/7-0 (det) (inlining.m:419)
  13   14* pred inlining:do_inlining/8-0 (det) (inlining.m:225 and
others)
  27       pred inlining:inlining/4-0 (det) (inlining.m:210)
  28       pred mercury_compile:maybe_do_inlining/6-0 (det)
(mercury_compile.m:1711)
  29       pred mercury_compile:middle_pass/5-0 (det)
(mercury_compile.m:1032)
  30       pred mercury_compile:mercury_compile/3-0 (det)
(mercury_compile.m:437)
  31       pred mercury_compile:compile/4-0 (det)
(mercury_compile.m:383)
  32       pred list:foldl/4-0 (det) (list.m:994)
  33       pred mercury_compile:process_module/7-0 (det)
(mercury_compile.m:325)
  34       pred mercury_compile:process_file_name/4-0 (det)
(mercury_compile.m:252)
  35       pred mercury_compile:process_arg/4-0 (det)
(mercury_compile.m:205)
  36       pred mercury_compile:process_arg_list_2/4-0 (det)
(mercury_compile.m:178)
  37       pred mercury_compile:process_arg_list/4-0 (det)
(mercury_compile.m:140)
  38       pred mercury_compile:main_2/5-0 (det) (mercury_compile.m:105)
  39       pred mercury_compile:main/2-0 (det) (mercury_compile.m:78)

Data in maps which are arguments to the call to merge:
  First map:
    var(1) -> typeclass_info(var(25), 1)
    var(2) -> typeclass_info(var(25), 2)
  Second map:
    var(2) -> type_info(var(27))


Probably the easiest way to get a handle on this (and verify that it
indeed has nothing to do with the rbtree module or any of my debugging
hacks) is to change the implementation of merge in some pristine sources
so that it does actually flag duplicated keys.  The current
implementation is:

map__merge(M0, M1, M) :-
        map__to_assoc_list(M0, ML0),
        map__to_assoc_list(M1, ML1),
        list__merge(ML0, ML1, ML),
        map__from_sorted_assoc_list(ML, M).

I always thought this was a bit of an odd way to implement it, even if
it was nice and clean.  I'd suggest something like:

map__merge(M0, M1, M) :-
        map__to_assoc_list(M1, ML1),
        map__det_insert_from_assoc_list(M0, ML1, M).

(or the reverse, adding the contents of M0 to M1, if one thinks perhaps
M1 tends to be bigger than M0).

Then bootcheck the compiler, and see if it barfs.

If it doesn't, then I apologise, but unfortunately I can't afford to
spend any more time on this.  Particularly since it looks like the
rbtree module needs work to avoid needless inefficiencies...  I'll stick
with the tree234 module (for now, anyway).

Cheers,
Warwick
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------