[m-rev.] for review: fix infinite loop for `:- inst x == x.'

[Mark Brown]

On 21-Nov-2002, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> Estimated hours taken: 1
> Branches: main, release
> 
> compiler/inst_match.m:
> 	Fix a bug where the compiler was going into an infinite loop
> 	for infinitely recursive insts, e.g. `:- inst foo == foo.'
> 
> 	XXX Note that we still don't handle cases such as
> 	`:- inst foo(I) == foo(list(I))' correctly.
> 	In those cases, the compiler will eventually run out of heap space.

An alternative solution to this problem may be to do a pass over all the
inst equivalence declarations to check for circularities, before mode
analysis even starts.  One way that this may be better is that errors
such as

	:- inst f == f.

would be detected even if the inst is never used.

> 
> Workspace: /home/mars/fjh/ws1/mercury
> Index: compiler/inst_match.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/inst_match.m,v
> retrieving revision 1.50
> diff -u -d -r1.50 inst_match.m
> --- compiler/inst_match.m	20 Mar 2002 12:36:24 -0000	1.50
> +++ compiler/inst_match.m	20 Nov 2002 19:16:37 -0000
> @@ -776,9 +778,24 @@
>  %-----------------------------------------------------------------------------%
>  
>  inst_expand(ModuleInfo, Inst0, Inst) :-
> +	set__init(Expansions),
> +	inst_expand_2(ModuleInfo, Inst0, Expansions, Inst).
> +
> +:- pred inst_expand_2(module_info, inst, set(inst_name), inst).
> +:- mode inst_expand_2(in, in, in, out) is det.
> +
> +inst_expand_2(ModuleInfo, Inst0, Expansions0, Inst) :-
>  	( Inst0 = defined_inst(InstName) ->
> -		inst_lookup(ModuleInfo, InstName, Inst1),
> -		inst_expand(ModuleInfo, Inst1, Inst)
> +		( set__member(InstName, Expansions0) ->
> +			% The inst is an infinitely recursive inst,
> +			% e.g. `:- inst foo == foo.'
> +			% We treat these as equivalent to `not_reached'.
> +			Inst = not_reached
> +		;
> +			set__insert(Expansions0, InstName, Expansions1),
> +			inst_lookup(ModuleInfo, InstName, Inst1),
> +			inst_expand_2(ModuleInfo, Inst1, Expansions1, Inst)
> +		)
>  	;
>  		Inst = Inst0
>  	).

It seems to me that the only way this can loop is if, when expanding a
particular user defined inst f/N, the same inst constructor f/N is reached
at the top level of the expanded inst.  Perhaps I've overlooked something,
but it should be sufficient for the Expansions argument to have type
set(sym_name_and_arity), and only be checked/updated when the inst is of
the form defined_inst(user_inst(_, _)).  This approach would also solve the
XXX in the log message.

Cheers,
Mark.

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------