I can describe for you how we do that efficiently in the “real” C# IDE.
The first thing we do is run a pass which analyzes only the “top level” stuff in the source code. We skip all the method bodies. That allows us to quickly build up a database of information about what namespace, types and methods (and constructors, etc) are in the source code of the program. Analyzing every single line of code in every method body would take way too long if you’re trying to do it between keystrokes.
When the IDE needs to work out the type of a particular expression inside a method body — say you’ve typed “foo.” and we need to figure out what are the members of foo — we do the same thing; we skip as much work as we reasonably can.
We start with a pass which analyzes only the local variable declarations within that method. When we run that pass we make a mapping from a pair of “scope” and “name” to a “type determiner”. The “type determiner” is an object that represents the notion of “I can work out the type of this local if I need to”. Working out the type of a local can be expensive so we want to defer that work if we need to.
We now have a lazily-built database that can tell us the type of every local. So, getting back to that “foo.” — we figure out which statement the relevant expression is in and then run the semantic analyzer against just that statement. For example, suppose you have the method body:
String x = "hello";
var y = x.ToCharArray();
var z = from foo in y where foo.
and now we need to work out that foo is of type char. We build a database that has all the metadata, extension methods, source code types, and so on. We build a database that has type determiners for x, y and z. We analyze the statement containing the interesting expression. We start by transforming it syntactically to
var z = y.Where(foo=>foo.
In order to work out the type of foo we must first know the type of y. So at this point we ask the type determiner “what is the type of y”? It then starts up an expression evaluator which parses x.ToCharArray() and asks “what’s the type of x”? We have a type determiner for that which says “I need to look up “String” in the current context”. There is no type String in the current type, so we look in the namespace. It’s not there either so we look in the using directives and discover that there’s a “using System” and that System has a type String. OK, so that’s the type of x.
We then query System.String’s metadata for the type of ToCharArray and it says that it’s a System.Char[]. Super. So we have a type for y.
Now we ask “does System.Char[] have a method Where?” No. So we look in the using directives; we have already precomputed a database containing all of the metadata for extension methods that could possibly be used.
Now we say “OK, there are eighteen dozen extension methods named Where in scope, do any of them have a first formal parameter whose type is compatible with System.Char[]?” So we start a round of convertibility testing. However, the Where extension methods are generic, which means we have to do type inference.
I’ve written a special type infererencing engine that can handle making incomplete inferences from the first argument to an extension method. We run the type inferrer and discover that there is a Where method that takes an IEnumerable<T>, and that we can make an inference from System.Char[] to IEnumerable<System.Char>, so T is System.Char.
The signature of this method is Where<T>(this IEnumerable<T> items, Func<T, bool> predicate), and we know that T is System.Char. Also we know that the first argument inside the parentheses to the extension method is a lambda. So we start up a lambda expression type inferrer that says “the formal parameter foo is assumed to be System.Char”, use this fact when analyzing the rest of the lambda.
We now have all the information we need to analyze the body of the lambda, which is “foo.”. We look up the type of foo, we discover that according to the lambda binder it is System.Char, and we’re done; we display type information for System.Char.
And we do everything except the “top level” analysis between keystrokes. That’s the real tricky bit. Actually writing all the analysis is not hard; it’s making it fast enough that you can do it at typing speed that is the real tricky bit.