[svn] r7387: nemerle/trunk/ncc/typing: StaticTyVar.n TyVarEnv.n

[VladD2]

Log:
Fix 875: Added detection of cyclic constraints.

Author: VladD2
Date: Tue Feb  6 04:59:35 2007
New Revision: 7387

Modified:
   nemerle/trunk/ncc/typing/StaticTyVar.n
   nemerle/trunk/ncc/typing/TyVarEnv.n

Modified: nemerle/trunk/ncc/typing/StaticTyVar.n
==============================================================================
--- nemerle/trunk/ncc/typing/StaticTyVar.n	(original)
+++ nemerle/trunk/ncc/typing/StaticTyVar.n	Tue Feb  6 04:59:35 2007
@@ -136,10 +136,6 @@
             (special & ~GenericParameterAttributes.NotNullableValueTypeConstraint))
         Message.Error ("`struct' generic constraint cannot be used together with `class' or `new ()'");
 
-      foreach (TyVarRef (tv) in subtype)
-        when (tv.Equals (this)) 
-          Message.Error ("cyclic constraint on type variable " + this.ToString ());
-        
       this.special = special;
       Constraints = subtype;
     }

Modified: nemerle/trunk/ncc/typing/TyVarEnv.n
==============================================================================
--- nemerle/trunk/ncc/typing/TyVarEnv.n	(original)
+++ nemerle/trunk/ncc/typing/TyVarEnv.n	Tue Feb  6 04:59:35 2007
@@ -395,6 +395,7 @@
         (map.Replace (name, tv_obj), tv_obj :: the_list)
       }
       def (m, l) = List.FoldLeft (tp.tyvars, (this.tyvars, []), loop);
+      def tyParams = l.Rev();
       def tenv = TyVarEnv (Manager, m);
       tenv.triggerObsolete = this.triggerObsolete;
 
@@ -435,13 +436,75 @@
         }
       }  
       
-      foreach (tv : StaticTyVar in l) {
+      mutable isConstraintsCyclic = false;
+
+
+      def tryDetectCyclicConstraints ()
+      {
+        def graph = Hashtable();
+
+        def tryFindCyclicConstraint (tyRef)
+        {
+          foreach (tv : StaticTyVar in tyParams)
+            graph[tv.id] = false;  // reset 'visited' flags
+
+          def scan (tyRef, path = []) // travers constraint dependency path
+          {
+            mutable visited;
+            if (graph.TryGetValue (tyRef.id, out visited))
+            { // tyRef is type parametr...
+              if (visited)
+                tyRef.Name :: path // and already visited
+              else
+              { // first visit
+                graph[tyRef.id] = true; // mark type parametr as visited
+                mutable constraint;
+                if (constraints.TryGetValue(tyRef.id, out constraint))
+                { // type parametr have constraints... foreach constraint...
+                  foreach (TyVarRef (subTyRef) in constraint[1])
+                  {
+                    def res = scan(subTyRef, path);
+                    unless (res.IsEmpty) // if we find cicle... ignore other...
+                      Nemerle.Imperative.Return (tyRef.Name :: res);
+                  }
+
+                  if (path.IsEmpty) [] else tyRef.Name :: path
+                }
+                else path
+              }
+            }
+            else path
+          }
+
+          def path = scan (tyRef);
+          unless (path.IsEmpty)
+          { // We have cycle! Extract information about it...
+            isConstraintsCyclic = true;
+            def info = path.ToString(" => ");
+            def tyParam = path.Head;
+            Message.Error ( // try find location of type parametr
+              match (tp.tyvars.Find(x => x.ToString() == tyParam)) {
+                | Some(name) => name.Location
+                | _          => Location.Default
+              },
+              $"A constraint of '$tyParam' type parameter is cyclic ($info)");
+          }
+        }
+
+        foreach (tv : StaticTyVar in tyParams)
+          tryFindCyclicConstraint(tv);
+      }
+
+      unless (tyParams.IsEmpty)
+        tryDetectCyclicConstraints ();
+
+      unless (isConstraintsCyclic)
+        foreach (tv : StaticTyVar in tyParams)
         // FIXME: check Intersection invariants and flag error
         // to the user, otherwise we'll get an ICE
         tv.SetConstraints (get (tv.id)); 
-      }
       
-      (tenv, List.Rev (l))
+      (tenv, tyParams)
     }
   }
 }