[m-rev.] diff: speed up parsing of d.u. types with many constructors

[Julien Fischer]

Estimated hours taken: 2
Branches: main

Fix one of the problems that causes the compiler to run out of stack
space when compiling a discriminated unions that has a large numbers of
constructors.  This speeds up compilation of a type with 200000 constructors
by about 1% -- it doesn't have a measurable impact on discriminated unions
of a more usual size.

compiler/prog_io.m:
 	When checking that the constructors of a discriminated union
 	are well-formed, iterate through the list of constructors once instead
 	of four times.

Julien.

Index: compiler/prog_io.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/prog_io.m,v
retrieving revision 1.284
diff -u -r1.284 prog_io.m
--- compiler/prog_io.m	31 Oct 2007 03:58:29 -0000	1.284
+++ compiler/prog_io.m	14 Nov 2007 02:17:04 -0000
@@ -2668,64 +2668,69 @@
      maybe1(processed_type_body)::out) is det.

  process_du_type_2(Functor, Params, Body, Ctors, MaybeUserEqComp, Result) :-
+    process_du_ctors(Params, Ctors, CtorsResult),
      (
-        % Check that all type variables in the body are either explicitly
-        % existentially quantified or occur in the head.
+        CtorsResult = ok,
+        TypeDefn = parse_tree_du_type(Ctors, MaybeUserEqComp),
+        ProcessedTypeBody = processed_type_body(Functor, Params, TypeDefn),
+        Result = ok1(ProcessedTypeBody)
+    ;
+        CtorsResult = error(Msg),
+        Result = error1([Msg - Body])
+    ).

-        list.member(Ctor, Ctors),
-        Ctor = ctor(ExistQVars, _Constraints, _CtorName, CtorArgs, _Ctxt),
+:- pred process_du_ctors(list(type_param)::in, list(constructor)::in,
+    maybe_error::out) is det.
+
+process_du_ctors(_Params, [],  ok).
+process_du_ctors(Params, [Ctor | Ctors], Result) :- 
+    Ctor = ctor(ExistQVars, Constraints, _CtorName, CtorArgs, _Conetxt),
+    (
+        % Check that all type variables in the ctor are either explicitly
+        % existentially quantified or occur in the head of the type.
+        %
          CtorArgTypes = list.map(func(C) = C ^ arg_type, CtorArgs),
          type_list_contains_var(CtorArgTypes, Var),
          \+ list.member(Var, ExistQVars),
          \+ list.member(Var, Params)
      ->
-        Msg = "free type parameter in RHS of type definition",
-        Result = error1([Msg - Body])
+        Result = error("free type parameter in RHS of type definition")
      ;
          % Check that all type variables in existential quantifiers do not
          % occur in the head (maybe this should just be a warning, not an error?
          % If we were to allow it, we would need to rename them apart.)
-
-        list.member(Ctor, Ctors),
-        Ctor = ctor(ExistQVars, _Constraints, _CtorName, _CtorArgs, _Ctxt),
+        %
          list.member(Var, ExistQVars),
          list.member(Var, Params)
      ->
-        Msg = "type variable has overlapping scopes " ++
-            "(explicit type quantifier shadows argument type)",
-        Result = error1([Msg - Body])
+        Result = error("type variable has overlapping scopes " ++
+            "(explicit type quantifier shadows argument type)")
      ;
          % Check that all type variables in existential quantifiers occur
          % somewhere in the constructor argument types or constraints.
-
-        list.member(Ctor, Ctors),
-        Ctor = ctor(ExistQVars, Constraints, _CtorName, CtorArgs, _Ctxt),
+        %
          list.member(Var, ExistQVars),
          CtorArgTypes = list.map(func(C) = C ^ arg_type, CtorArgs),
          \+ type_list_contains_var(CtorArgTypes, Var),
          constraint_list_get_tvars(Constraints, ConstraintTVars),
          \+ list.member(Var, ConstraintTVars)
-    ->
-        Msg = "type variable in existential quantifier " ++
-            "does not occur in arguments or constraints of constructor",
-        Result = error1([Msg - Body])
+    -> 
+        Result = error("type variable in existential quantifier " ++
+            "does not occur in arguments or constraints of constructor")
      ;
          % Check that all type variables in existential constraints occur in
          % the existential quantifiers.
-
-        list.member(Ctor, Ctors),
-        Ctor = ctor(ExistQVars, Constraints, _CtorName, _CtorArgs, _Ctxt),
+        %
          list.member(Constraint, Constraints),
          Constraint = constraint(_Name, ConstraintArgs),
          type_list_contains_var(ConstraintArgs, Var),
          \+ list.member(Var, ExistQVars)
      ->
-        Msg = "type variables in class constraints introduced with `=>' " ++
-            "must be explicitly existentially quantified using `some'",
-        Result = error1([Msg - Body])
+        Result = error("type variables in class constraints introduced" ++
+            " with `=>' must be explicitly existentially quantified" ++
+            " using `some'")
      ;
-        Result = ok1(processed_type_body(Functor, Params,
-            parse_tree_du_type(Ctors, MaybeUserEqComp)))
+        process_du_ctors(Params, Ctors, Result)
      ).

  %-----------------------------------------------------------------------------%

--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------