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

[Fergus Henderson]

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.

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
@@ -159,7 +159,8 @@
 /*
 ** Predicates to test various properties of insts.
 ** Note that `not_reached' insts are considered to satisfy
-** all of these predicates except inst_is_clobbered.
+** all of these predicates except inst_is_clobbered, inst_is_free,
+** and inst_is_bound_to_functors.
 */
 
         % succeed if the inst is fully ground (i.e. contains only
@@ -196,6 +197,7 @@
 :- pred inst_is_not_fully_unique(module_info, inst).
 :- mode inst_is_not_fully_unique(in, in) is semidet.
 
+        % succeed if the inst passed is `clobbered' or `mostly_clobbered'
 :- pred inst_is_clobbered(module_info, inst).
 :- mode inst_is_clobbered(in, in) is semidet.
 
@@ -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
 	).
@@ -1080,65 +1097,141 @@
         % or `mostly_clobbered' or if it is a user-defined inst which
         % is defined as one of those.
 
-inst_is_clobbered(_, not_reached) :- fail.
-inst_is_clobbered(_, any(mostly_clobbered)).
-inst_is_clobbered(_, any(clobbered)).
-inst_is_clobbered(_, ground(clobbered, _)).
-inst_is_clobbered(_, ground(mostly_clobbered, _)).
-inst_is_clobbered(_, bound(clobbered, _)).
-inst_is_clobbered(_, bound(mostly_clobbered, _)).
-inst_is_clobbered(_, inst_var(_)) :-
+        % The third arg for the _2 version is the set of insts which have
+        % already been expanded - we use this to avoid going into an
+        % infinite loop for infinitely recursive insts.
+
+inst_is_clobbered(ModuleInfo, Inst) :-
+	set__init(Expansions),
+	inst_is_clobbered_2(ModuleInfo, Inst, Expansions).
+
+:- pred inst_is_clobbered_2(module_info, inst, set(inst_name)).
+:- mode inst_is_clobbered_2(in, in, in) is semidet.
+inst_is_clobbered_2(_, not_reached, _) :- fail.
+inst_is_clobbered_2(_, any(mostly_clobbered), _).
+inst_is_clobbered_2(_, any(clobbered), _).
+inst_is_clobbered_2(_, ground(clobbered, _), _).
+inst_is_clobbered_2(_, ground(mostly_clobbered, _), _).
+inst_is_clobbered_2(_, bound(clobbered, _), _).
+inst_is_clobbered_2(_, bound(mostly_clobbered, _), _).
+inst_is_clobbered_2(_, inst_var(_), _) :-
         error("internal error: uninstantiated inst parameter").
-inst_is_clobbered(ModuleInfo, constrained_inst_vars(_, Inst)) :-
-	inst_is_clobbered(ModuleInfo, Inst).
-inst_is_clobbered(ModuleInfo, defined_inst(InstName)) :-
-        inst_lookup(ModuleInfo, InstName, Inst),
-        inst_is_clobbered(ModuleInfo, Inst).
+inst_is_clobbered_2(ModuleInfo, constrained_inst_vars(_, Inst), Expansions) :-
+	inst_is_clobbered_2(ModuleInfo, Inst, Expansions).
+inst_is_clobbered_2(ModuleInfo, defined_inst(InstName), Expansions0) :-
+        ( set__member(InstName, Expansions0) ->
+		% It's an infinitely recursive inst,
+		% e.g. :- inst foo == foo.
+		% We treat these as equivalent to `not_reached' insts.
+                fail
+        ;
+                set__insert(Expansions0, InstName, Expansions),
+		inst_lookup(ModuleInfo, InstName, Inst),
+		inst_is_clobbered_2(ModuleInfo, Inst, Expansions)
+	).
 
         % inst_is_free succeeds iff the inst passed is `free'
         % or is a user-defined inst which is defined as `free'.
         % Abstract insts must not be free.
 
-inst_is_free(_, free).
-inst_is_free(_, free(_Type)).
-inst_is_free(_, inst_var(_)) :-
+        % The third arg for the _2 version is the set of insts which have
+        % already been expanded - we use this to avoid going into an
+        % infinite loop for infinitely recursive insts.
+
+inst_is_free(ModuleInfo, Inst) :-
+	set__init(Expansions),
+	inst_is_free_2(ModuleInfo, Inst, Expansions).
+
+:- pred inst_is_free_2(module_info, inst, set(inst_name)).
+:- mode inst_is_free_2(in, in, in) is semidet.
+inst_is_free_2(_, not_reached, _) :- fail.
+inst_is_free_2(_, free, _).
+inst_is_free_2(_, free(_Type), _).
+inst_is_free_2(_, inst_var(_), _) :-
         error("internal error: uninstantiated inst parameter").
-inst_is_free(ModuleInfo, constrained_inst_vars(_, Inst)) :-
-	inst_is_free(ModuleInfo, Inst).
-inst_is_free(ModuleInfo, defined_inst(InstName)) :-
-        inst_lookup(ModuleInfo, InstName, Inst),
-        inst_is_free(ModuleInfo, Inst).
+inst_is_free_2(ModuleInfo, constrained_inst_vars(_, Inst), Expansions) :-
+	inst_is_free_2(ModuleInfo, Inst, Expansions).
+inst_is_free_2(ModuleInfo, defined_inst(InstName), Expansions0) :-
+	( set__member(InstName, Expansions0) ->
+		% It's an infinitely recursive inst,
+		% e.g. :- inst foo == foo.
+		% We treat these as equivalent to `not_reached' insts.
+                fail
+        ;
+                set__insert(Expansions0, InstName, Expansions),
+		inst_lookup(ModuleInfo, InstName, Inst),
+		inst_is_free_2(ModuleInfo, Inst, Expansions)
+	).
 
         % inst_is_bound succeeds iff the inst passed is not `free'
         % or is a user-defined inst which is not defined as `free'.
         % Abstract insts must be bound.
 
-inst_is_bound(_, not_reached).
-inst_is_bound(_, any(_)).
-inst_is_bound(_, ground(_, _)).
-inst_is_bound(_, bound(_, _)).
-inst_is_bound(_, inst_var(_)) :-
+        % The third arg for the _2 version is the set of insts which have
+        % already been expanded - we use this to avoid going into an
+        % infinite loop for infinitely recursive insts.
+
+inst_is_bound(ModuleInfo, Inst) :-
+	set__init(Expansions),
+	inst_is_free_2(ModuleInfo, Inst, Expansions).
+
+:- pred inst_is_bound_2(module_info, inst, set(inst_name)).
+:- mode inst_is_bound_2(in, in, in) is semidet.
+inst_is_bound_2(_, not_reached, _).
+inst_is_bound_2(_, any(_), _).
+inst_is_bound_2(_, ground(_, _), _).
+inst_is_bound_2(_, bound(_, _), _).
+inst_is_bound_2(_, inst_var(_), _) :-
         error("internal error: uninstantiated inst parameter").
-inst_is_bound(ModuleInfo, constrained_inst_vars(_, Inst)) :-
-	inst_is_bound(ModuleInfo, Inst).
-inst_is_bound(ModuleInfo, defined_inst(InstName)) :-
-        inst_lookup(ModuleInfo, InstName, Inst),
-        inst_is_bound(ModuleInfo, Inst).
-inst_is_bound(_, abstract_inst(_, _)).
+inst_is_bound_2(ModuleInfo, constrained_inst_vars(_, Inst), Expansions) :-
+	inst_is_bound_2(ModuleInfo, Inst, Expansions).
+inst_is_bound_2(ModuleInfo, defined_inst(InstName), Expansions0) :-
+	( set__member(InstName, Expansions0) ->
+		% It's an infinitely recursive inst,
+		% e.g. :- inst foo == foo.
+		% We treat these as equivalent to `not_reached' insts.
+                true
+        ;
+                set__insert(Expansions0, InstName, Expansions),
+		inst_lookup(ModuleInfo, InstName, Inst),
+		inst_is_bound_2(ModuleInfo, Inst, Expansions)
+	).
+inst_is_bound_2(_, abstract_inst(_, _), _).
 
         % inst_is_bound_to_functors succeeds iff the inst passed is
         % `bound(_Uniq, Functors)' or is a user-defined inst which expands to
         % `bound(_Uniq, Functors)'.
 
-inst_is_bound_to_functors(_, bound(_Uniq, Functors), Functors).
-inst_is_bound_to_functors(_, inst_var(_), _) :-
+        % The third arg for the _2 version is the set of insts which have
+        % already been expanded - we use this to avoid going into an
+        % infinite loop for infinitely recursive insts.
+
+inst_is_bound_to_functors(ModuleInfo, Inst, Functors) :-
+	set__init(Expansions),
+	inst_is_bound_to_functors_2(ModuleInfo, Inst, Functors, Expansions).
+
+:- pred inst_is_bound_to_functors_2(module_info, inst, list(bound_inst),
+		set(inst_name)).
+:- mode inst_is_bound_to_functors_2(in, in, out, in) is semidet.
+inst_is_bound_to_functors_2(_, bound(_Uniq, Functors), Functors, _).
+inst_is_bound_to_functors_2(_, inst_var(_), _, _) :-
         error("internal error: uninstantiated inst parameter").
-inst_is_bound_to_functors(ModuleInfo, constrained_inst_vars(_, Inst),
-		Functors) :-
-	inst_is_bound_to_functors(ModuleInfo, Inst, Functors).
-inst_is_bound_to_functors(ModuleInfo, defined_inst(InstName), Functors) :-
-        inst_lookup(ModuleInfo, InstName, Inst),
-        inst_is_bound_to_functors(ModuleInfo, Inst, Functors).
+inst_is_bound_to_functors_2(ModuleInfo, constrained_inst_vars(_, Inst),
+		Functors, Expansions) :-
+	inst_is_bound_to_functors_2(ModuleInfo, Inst, Functors, Expansions).
+inst_is_bound_to_functors_2(ModuleInfo, defined_inst(InstName), Functors,
+		Expansions0) :-
+	( set__member(InstName, Expansions0) ->
+		% It's an infinitely recursive inst,
+		% e.g. :- inst foo == foo.
+		% We treat these as equivalent to `not_reached' insts.
+                fail
+        ;
+                set__insert(Expansions0, InstName, Expansions),
+		inst_lookup(ModuleInfo, InstName, Inst),
+		inst_is_bound_to_functors_2(ModuleInfo, Inst, Functors,
+			Expansions)
+	).
 
 %-----------------------------------------------------------------------------%
 

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------