The more things change

A while back we got an MSDN feedback report about a crash a customer
was experiencing.  The customer had the following code:

 class A : B {

class B : A {

class C : B {
     override //Type space here

At this point the IDE would just up and vanish.  What
happened?  Well, (as you can probably guess from the code snippet)
we wanted to pop up the "override completion list" so we attempt to
walk the entire inheritance chain to find the list of overridable
methods, infinitely recurse, and *poof* the IDE is gone.  Now,
there are a lot of features that need to walk the inheritance chain
(regular completion lists after <dot> for one), but they dont'
have this problem.  Why?  Well, in order to prevent this
problem we have a specialized search class that performs a depth first search (DFS) over the type system and thus doesn't run into this problem. 
Unfortunately, the "override completion list" didn't use this search
class, instead it would just explicitly call into methods like "GetSuperType()" in a while
loop, and thus didn't detect these circularities in teh graph.  So
this was pretty simple to fix.  We moved over to using the search
class, and we also did a full code review of all GetSuperType calls to
make sure they weren't doing anything similar that would cause problems.

However, in the whidbey time we recently discovered that this solution
was not good enough and we could still run into problems with
circularities.  How?  Well, consider the following code:

 interface ISet<A> : IMap<A,A> {<br>}<br>interface IMap
<A,B> : ISet<ITuple<A,B>> {<br>}<br>interface ITuple
<A,B> {<br>}<br>class C : IMap
<int,string> { //try to invoke implement-interface here<br>}

In this case we have a similar, but subtly different, problem going on
here.  Implement-Interface (II) does use the DFS-class, but in
this case that class no longer sufficed.  Why?  Well, the way
II works is that it walks the interface inheritance tree to determine
the set of methods that needs to be implemented.  Any methods that
aren't already implemented will then be stubbed out for you.  So
let's start trying to figure out the total set of interfaces
implemented by "class C".  We start with:

IMap<A,B> and we ask “what
interfaces do you have?” and we find out:

ISet<ITuple<A,B>> to which we ask what
interfaces do you have?” and we find out:

IMap<ITuple<A,B>,ITuple<A,B>> to which we ask to which
we ask “what interfaces do you have?”:

ISet<ITuple<ITuple<A,B>,ITuple<A,B>>> to which we ask to
which we ask “what interfaces do you have?”:


Ad infinitum.

So the question then arises "how can i determine the complete set of
interfaces that a class implements, while ensuring that recursive
generic definitions don't expand like above".  It's a rather fun
problem and so far i like the current solution we have for this.