Various improvements to semantic pre-analysis (pass 1).

Feature

I have a few ways in which the first analysis pass may be improved.
These are listed and discussed below, or in following comments.

Pitch

As I have been looking through semanal.py (mostly), tracking down a few different misbehaviors of mypy, I have found the code that deals with symbols and scopes to be confusing to me. I'd like to simplify things and make handling more consistent.

This will fix a few of these bugs, reduce the amount of code, improve the readability of the code, and possibly improve speed as well.

A lot of work in the semantic analyzer can be performed in the pre-analysis, with the results left in the various AST nodes. These can be reused by the later semantic and type analysis passes on the same module (which is why it could make things run faster).

Broad outline:

Currently, the pre-analysis of a module walks through most of the AST, including nested function and class defs. It skips some branches of the AST which hold nothing of interest.

1. It identifies code blocks which are unreachable, due to statically evaluated conditions of if statements and case guards.
2. It skips traversal of unreachable blocks. Later traversers can also skip them.
3. It identifies which import statements are in the global scope. (By the way, I suspect that later analysis won't catch an import being bound to a variable declared as global in a non-global scope).

I propose further that pre-analysis would do:

4. Collect information about the status of every unqualified name appearing in every reachable scope (module, function, and class). Comprehensions and generators are separate scopes.
5. Store this in the AST nodes, probably as SymbolTable objects.

Each name in the namespace can provide:

• The AST node where the name is first seen. This would be a NameExpr, and would supply a line number.
• What kind of variable it is:
  Global
  Nonlocal
  Local (i.e., has a binding in the scope, but none of the above)
  Free (none of the above. May be replaced by a Local while analyzing the scope)
• The location of the variable:
  For Local, it is a Var for the first occurrence of a binding within the scope.
  Otherwise, it is a Var for the same name as found in the namespaces, or None if the name was not found.
  Note, a binding of a global name in a non-global scope should be entered in the module symbol table if it is the first binding to that name found anywhere in the file.

Analysis will be performed breadth-first. That is, the entire body of a scope is analyzed, except for the bodies of contained function and class defs, followed by the scopes of said bodies, recursively.
This is so that any names that are not bound (so far) in the scope will have an exact known referent in another namespace. When the name is first encountered in the scope, not in a global or nonlocal declaration, the name will be entered as a Free variable along with what it refers to (if anything). If a binding is later encountered, then the Free variable entry is removed from the namespace and replaced with a Local variable, giving the node that caused the binding.

This is not intended to provide type information for the names in the namespaces.

The namespace provided for a class def can be used as the starting point for a TypeInfo for the class, to be augmented later as bindings of member names are analyzed in instance or class methods.

While the analyzer could maintain a stack of scopes currently being processed, I think it would be simpler code for each namespace to point back to its containing namespace. Any namespace will have enough information to resolve any names, even names it doesn't know about, after the pre-analysis is complete.

There is one case in which the module by itself cannot provide all information needed. That is from x import *, which must be at the module level. For any other import statements, the statement itself is the source of the bindings for the names (or more precisely, the first binding of a name if bound more than once). So depending on which names are actually exported by the imported module, some global bindings may change or be added. An import will override an existing binding if it occurs before the latter binding. A global name might be bound at runtime by an assignment to a global variable within a class definition, or more pathologically, an assignment within a function which is called at the module level. I don't think it's possible to always know which occurs first, so I would simplify things by assuming that if the import occurs before an assignment at module level, then that should be used. Anyway, the module does contain multiple places the global variable can be assigned, and analysis can check for type consistency.

To handle import * statements, I suggest a special import analysis pass over all the modules in an SCC, before doing any semantic analysis of any of them. The gist of this analysis is:

1. If any imported modules have __all__, then the import * will be replaced by import x, y, ... for all the names mentioned.
2. If any import * is guarded by MYPY or TYPE_CHECKING, consider these names not reexported and disregard the import statement. Likewise if for some other reason, imports are not implicitly reexported, do the same. The import statements will still be analyzed at a later stage
3. If there is a cycle of remaining import * statements, then collect all the global names in all the modules in the cycle, then consider them all imported into all of the modules, I would just arbitrarily pick one (perhaps the first module in the original processing order) and use that. Replace each import * with from x import y for all the collected names and the modules where those names were found.
4. Now we are left with only specifically named imports everywhere.
5. I think that the current algorithm for ordering the modules in the SCC should be sufficient to identify a definite result for each import. It might be necessary to follow a chain of imports to get to the module containing the desired name.
6. As a result, there should not be (though I could be wrong) any need to handle missing imported names by deferral. If a name is missing, it will remain missing forever. Thus, every import either produces a definite variable or an error.

Actually, this import analysis pass can be useful even without any import *s, starting with step 4.

Start with semanal.py and trace the current pre-analysis traversal, scope handling, and import processing described in the issue. The proposal spans AST nodes, namespaces, scopes, and strongly connected modules, but names no tests or bounded acceptance criteria. Before implementation, the scope and expected behavior would need to be made concrete.