Results vary with the order of the specified files.

[mrolle45]

I have a project with many modules. A group of 30 of them are in a cyclic import SCC.

I ran mypy under Visual Studio. While trying to see why some errors appeared, I ran a copy of the mypy code with a debugger. I noticed that I got quite a different set of errors reported.
The difference was that Visual Studio passes filenames to mypy in the order that it finds them in the project, whereas I used "mypy ." for the debugging. mypy processed the same set of input files, but in a different order.

I made a names file with the names in the order used by VS, and then ran mypy using this names file, with same result as running under VS.

I've collected log files from both runs. They include a bunch of extra messages which I put into my code, so as to help me figure out what was going on. It includes details about imports and symbol definitions in this SCC, and two files, cache and solver.common in particular.

I have attached a zip with these logs. It also includes just the error messages extracted from the logs. You will see the greatly different results. 148 errors in one case and 93 errors in the other case.

It's apparent to me that the order of the files in this SCC is what makes the difference. I will be looking at what in detail is different and why that is happening. It has something to do with marking a module as incomplete when it imports * from another incomplete module, and some, but not all, of the needed symbols are imported only during the final iteration.

However, in the meantime, here are the output files, if you want to see what you can make of them. The order of the SCC is shown in line 873 of each log file.
Exp.zip

[mrolle45]

Each mypy run has errors that are not in the other one.
Here is a diff between the two error files.
diff.err.txt
Most of the errors in the first file are names that were supposed to be imported indirectly from cache via solver.common. solver.common also has specific names that it could not import from cache.
Likewise for the second file, but involving different modules. Also, curiously, there are a few legitimate errors, which are not reported in the first file.

[mrolle45]

Here's a better pair of log files, with only the relevant differences:
log.txt
log2.txt

The Problem
semanal.py method SemanticAnalyzer.visit_import_all has the following logic:

			if self.is_incomplete_namespace(i_id):
				# Any names could be missing from the current namespace if the target module
				# namespace is incomplete.
				self.mark_incomplete('*', i)

The consequence of this is that from that point onward in the current module, no symbols will be added to the symbol table.
This is evident from both the log files, where import * from solver.debugging adds no symbols, even though there are plenty of symbols that can be imported. See:

LOG:      Module cache:
LOG:          import * from metaclasses
LOG:              (incomplete)
LOG:          import * from solver.debugging
                      --> Nothing here.
LOG:          import * from solver.common
LOG:              (incomplete)

This occurs until the final iteration (3). At this point, all modules have been deemed to be complete, and so
each module will add symbols that are imported as * from other modules. However, this only adds symbols that have so far been added to those modules' symbols. This explains why the order of the modules affects which symbols are found in the modules.

Questions

1. I don't understand why defining all new symbols is suppressed just because an import * had an unknown set of names, When a symbol is defined several times (in the same scope), the philosophy is that the type (inferred or explicit) of the first definition will become the type, and further definitions to an incompatible type will be reported as errors. Thus, a symbol definition might or might not be the first time if an earlier import * was incomplete.
   However, this is a matter of type analysis, not semantic analysis. Since semantic analysis is completely done before any type analysis of the same module (this is so, isn't it?), the semantic analysis can collect all the definitions of the symbol. If an earlier (in the scope) definition is found during a later iteration, does that matter? Is there a possibility of reporting an error that later would become not an error?
2. A similar question regarding the several places in the code where an individual symbol name is marked incomplete.

Possible solutions

1. When no progress is made during an iteration through the module list, check if there are any incomplete modules remaining. If so, then clear the incomplete modules set, but do not set self.final_iteration yet.
   There will be one, or possibly more, non-final iterations. Then when no further progress is made, that is the time to set self.final_iteration.
2. In addition, allow a symbol to be added to a symbol table even if that name, or *, has been marked as incomplete.
   I'm not sure what would happen in a later iteration when the original definition of the symbol is now resolved. If not, then this would have the effect of speeding up the analysis.
3. In addition, if importing * from a module which has been analyzed at least once and defines __all__, then simply add all those names to the symbol table. In some cases, they may be placeholders, and in a later iteration, if the imported module now has real definition for a symbol, it can replace the imported placeholder in the current symbol table.
   Again, you would have to verify that there would be no adverse consequences, and if so, this would have the effect of speeding up the analysis.

As can be seen from my log files, what is now the final iteration has not had the chance to add everything possible to the symbol tables, due to the order of the modules.

I will try solution 1 in my own copy of the code, and add a comment as to how it went, and if successful (with my own project), the actual code changes I made.

[mrolle45]

After making the suggested change, I encountered an infinite iteration. I constructed a simple example and this is reported in #12620.

The one-line change therein must be made along with the above solution # 1.

I also had a problem with a recursive NamedTuple class definition. I took out the NamedTuple base class in this case, so that I could proceed with mypy.

I still have the same situation. I now have 85 errors in one case and 131 errors in the other. Compare with 93 and 148 originally.

In both runs, there are 3 iterations until no more progress. Then after clearing the incomplete modules set, there are 2 more iterations, with no progress in the latter one. Then iteration 6 is the final iteration.

Stay tuned!

[mrolle45]

I noticed that in both cases, I got the "skipping most remaining errors" message. So I added many_errors_threshold = 0 to my mypy.ini file.
As a result there were now thousands of errors. But still not the same set of errors in both cases. So truncating the error messages was not the source of the problem.

Short example

I did, however, eventually find out why one name was missing in one run but not in the other.
Here's a simple example:

A.py:
from B import *     # should be importing Foo from B.

B.py:
from A import *
class Foo: pass

C.py:
from A import *
class Bar(Foo): pass   # should have imported Foo from A.

To reproduce the bug:

D:\Solutions\trunk\Python\Example>mypy A.py B.py C.py
Success: no issues found in 3 source files

D:\Solutions\trunk\Python\Example>mypy B.py A.py C.py
C.py:3: error: Name "Foo" is not defined
Found 1 error in 1 file (checked 3 source files)

Here's my enhanced log file for the second case. It shows the status of the name Foo in each module, both before and after it is processed each iteration.

LOG:  Processing SCC of size 2 (A B) as inherently stale with stale deps (builtins)
LOG:  Iteration 1:
LOG:      Module A:
              Name Foo not defined.
LOG:          import * from B
LOG:              (incomplete)
              Name Foo not defined.
LOG:          progress.
LOG:          deferred.
LOG:      Module B:
              Name Foo not defined.
LOG:          import * from A
LOG:              (incomplete)
              Name Foo not defined.
LOG:          progress.
LOG:          deferred.
LOG:  Iteration 2:
LOG:      Module A:
              Name Foo not defined.
LOG:          import * from B
LOG:              (incomplete)
              Name Foo not defined.
LOG:          deferred.
LOG:      Module B:
              Name Foo not defined.
LOG:          import * from A
LOG:              (incomplete)
              Name Foo not defined.
LOG:          deferred.
LOG:      Clearing incomplete namespaces.       --> From now on, the "import *"s will be processed.
LOG:  Iteration 3:
LOG:      Module A:
              Name Foo not defined.
LOG:          import * from B      --> A.Foo not imported because it doesn't exist yet in B.
              Name Foo not defined.
LOG:          complete.
                 --> not deferred, no progress.  Therefore, A won't be in the remaining iterations.
LOG:      Module B:
              Name Foo not defined.
LOG:          import * from A
LOG:          add symbol: B.Foo from line 3    --> Defines B.Foo, but too late to import to A.Foo.
              B.Foo found
LOG:          progress.
LOG:          complete.
                 --> not deferred, but progress.  Therefore, B will be in the next iteration.
LOG:  Iteration 4:
LOG:      Module B:
              B.Foo found
LOG:          import * from A
              B.Foo found
LOG:          complete.
LOG:  Processing SCC singleton (C) as inherently stale with stale deps (A builtins)
LOG:  Iteration 1:
LOG:      Module C:
              Name Foo not defined.
LOG:          import * from A     --> There's no A.Foo
LOG:          add symbol: C.Bar from line 3
LOG:              (placeholder)
              Name Foo not defined.
LOG:          progress.
LOG:          complete.
LOG:          deferred.
LOG:  Iteration 2:
LOG:      Module C:
              Name Foo not defined.
LOG:          import * from A     --> There's still no A.Foo, of course.
LOG:          add symbol: C.Bar from line 3
              Name Foo not defined.
LOG:          progress.
LOG:          complete.
LOG:  Iteration 3:
LOG:      Module C:
              Name Foo not defined.
LOG:          import * from A     --> There's still no A.Foo, of course.
              Name Foo not defined.
LOG:          complete.
C.py:3: error: Name "Foo" is not defined
Found 1 error in 1 file (checked 3 source files)

The problem

In iteration 3, A's import from B should recognize that B is not yet complete, because it doesn't know what all its names are. The code currently looks for 'B' in analyzer.incomplete_modules, but we already cleared it. So the import from B brings in the names which are currently defined in B (which does not include B.Foo). No deferral is flagged. Therefore, A doesn't get a second chance.

Possible fix

The module's (in)complete status should be an attribute of the module (MyPyFile) object, rather than its name being in analyzer.incomplete_modules. If this is the only place where incomplete_modules is used, then that member of SemanticAnalyzer can be dropped.

When a module does an import * from another module, if the imported module is incomplete, then the importing module should remain incomplete, and be deferred.

In my example, in iteration 3, A will remain incomplete, and will be deferred. B will define B.Foo, and remain incomplete and deferred, and report progress. In iteration 4, A.Foo will now be imported from B, and report progress. Both modules will still be incomplete and deferred. In iteration 5, the same, except that neither A nor B has any progress. Then iteration 6 will be the final iteration, analyzing A and B. Later, module C will find A.Foo and all is well.

Suggested further improvements, which will improve performance:

1. When visiting an import * from B, if the B defines __all__, then treat this as an import of each of its specified names. Thus it won't affect any later definitions of some different names.
2. If B not define __all__, then calculate all the names, and their definitions, which would eventually be defined in B after items get imported from one module to the next. Ignore the (in)complete status of B. This is recursive. The result starts with all the currently known public names in B. If B has any from C import * statements, then do the same for C and add these imported names to the result for B. If C is one of the modules (including A) which are being examined, then skip the recursion. In this way, you will have the set of all public names in all the modules involved.
   This recursion will also prevent going over the iteration limit in a (rather sadistic) case of 20+ modules which each import * from the next in a single cycle. In a well-designed hierarchy of modules, where A1 depends on A2, ..., which depends on A20, A20 might want something from from A1, perhaps in a type annotation. So instead of importing that specific name from A1, it would import * from A1.

I'll try implementing these possible fixes and see if I get the results I want, both from the short example and from the large project I started with.

Results will be posted later today or tomorrow.

[mrolle45]

Good news
My fix works in the simpler example (with A, B, and C). In iteration 3, A imports from still incomplete B, and is now incomplete and deferred. In iteration 4, A imports from now complete B, and gets A.Foo. The import of B into C now gets Foo.
Bad news so far
It still doesn't work in the original larger example. This is because solver.common specifically imports cache.cache_property, but since the latter does not (yet) exist, solver.common.cache_property is considered private. Even though there is another iteration for solver.common, and cache.cache_property now exists, the status of solver.common.cache_property remains private.
Another fix
If B.x is imported into A, and if A.x is already defined but private, then treat this as a "valid replacement" for A.x. This will set A.progress, so anything that depends on A.x has a chance to get updated. If A.x and B.x are not the same symbol, it would not be a valid replacement.
I'm going to try this fix right now, stay tuned for the result!

[mrolle45]

Another problem.

When there is a missing imported name, a Var node is created as a placeholder, rather than a PlaceholderNode. This symbol is private.
As a result, my fix using extra analysis iterations doesn't work. After the missing name is encountered, in a later iteration the name is found. In my example, Foo is a function. When trying to add it to the A symbol table, this fails, because the existing symbol has a Var node, while the added symbol has a FuncDef node.
The imported name var works fine, because it is a variable, rather than a function.
However, in both cases the resulting symbols are private, and so cannot be imported into some other module.

This behavior is dependent on the order of the module names on the command line.

Details:

A.py:
import typing
from B import *
if typing.TYPE_CHECKING:
	from B import Foo, var

Foo()
Bar(None)
myvar = var

B.py:
from typing import NamedTuple, Optional, Tuple, Callable

from A import *

def Foo(): pass

class Bar(NamedTuple):
	next: Optional[Bar]

var: int = 42

mypy -v B.py A.py

LOG:  Processing SCC of size 2 (A B) as inherently stale
LOG:  Iteration 1:
LOG:      Module A:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from B
LOG:              (incomplete)
LOG:          import Foo from B
LOG:              (incomplete)
LOG:          import var from B
LOG:              (incomplete)
LOG:          After:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          progress.
LOG:          deferred.
LOG:      Module B:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from A
LOG:              (incomplete)
LOG:          After:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          progress.
LOG:          deferred.
LOG:  Iteration 2:
LOG:      Module A:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from B
LOG:              (incomplete)
LOG:          import Foo from B
LOG:              (incomplete)
LOG:          import var from B
LOG:              (incomplete)
LOG:          After:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          deferred.
LOG:      Module B:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from A
LOG:              (incomplete)
LOG:          After:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          deferred.
LOG:      Clearing incomplete namespaces.
LOG:  Iteration 3:
LOG:      Module A:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from B
LOG:              (incomplete)
LOG:          import Foo from B
LOG:              (incomplete)
LOG:          error message: A 4:1 Module "B" has no attribute "Foo"
LOG:          add symbol: A.Foo (Var) (private) from line -1      --> Should be a placeholder.
LOG:          import var from B
LOG:              (incomplete)
LOG:          error message: A 4:1 Module "B" has no attribute "var"
LOG:          add symbol: A.var (Var) (private) from line -1
LOG:          add symbol: A.myvar (Var) from line 8
LOG:          After:
LOG:            A.Foo (Var) (private) found
LOG:            Name Bar not defined.
LOG:            A.var (Var) (private) found
LOG:          progress.
LOG:          deferred.
LOG:      Module B:
LOG:          Before:
LOG:            Name Foo not defined.
LOG:            Name Bar not defined.
LOG:            Name var not defined.
LOG:          import * from A
LOG:              (incomplete)
LOG:          add symbol: A.myvar (Var) from line 8
LOG:          add symbol: B.Foo (FuncDef) from line 5
LOG:          add symbol: B.Bar (PlaceholderNode) from line 7
LOG:          add symbol: B.var (Var) from line 11
LOG:          After:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          progress.
LOG:          deferred.
LOG:  Iteration 4:
LOG:      Module A:
LOG:          Before:
LOG:            A.Foo (Var) (private) found
LOG:            Name Bar not defined.
LOG:            A.var (Var) (private) found
LOG:          import * from B
LOG:              (incomplete)
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)     --> Symbol not replaced.
LOG:          add symbol: B.Bar (PlaceholderNode) from line 7
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          import Foo from B
LOG:              (incomplete)
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)
LOG:          import var from B
LOG:              (incomplete)
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          After:
LOG:            A.Foo (Var) (private) found        --> Still in the symbol table.
LOG:            B.Bar (PlaceholderNode) found
LOG:            A.var (Var) (private) found
LOG:          progress.
LOG:          deferred.
LOG:      Module B:
LOG:          Before:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          import * from A
LOG:              (incomplete)
LOG:          After:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          deferred.
LOG:  Iteration 5:
LOG:      Module A:
LOG:          Before:
LOG:            A.Foo (Var) (private) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            A.var (Var) (private) found
LOG:          import * from B
LOG:              (incomplete)
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          import Foo from B
LOG:              (incomplete)
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)
LOG:          import var from B
LOG:              (incomplete)
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          After:
LOG:            A.Foo (Var) (private) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            A.var (Var) (private) found
LOG:          deferred.
LOG:      Module B:
LOG:          Before:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          import * from A
LOG:              (incomplete)
LOG:          After:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          deferred.
LOG:  Iteration 6 (final):
LOG:      Module A:
LOG:          Before:
LOG:            A.Foo (Var) (private) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            A.var (Var) (private) found
LOG:          import * from B
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)
LOG:          add symbol: A.Bar (Var) from line -1
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          import Foo from B
LOG:              Import B.Foo (FuncDef) over A.Foo (Var) (private)
LOG:          import var from B
LOG:              Import B.var (Var) over A.var (Var) (private)
LOG:          After:
LOG:            A.Foo (Var) (private) found        --> should be FuncDef and public
LOG:            A.Bar (Var) found
LOG:            A.var (Var) (private) found        --> should be public
LOG:          complete.
LOG:      Module B:
LOG:          Before:
LOG:            B.Foo (FuncDef) found
LOG:            B.Bar (PlaceholderNode) found
LOG:            B.var (Var) found
LOG:          import * from A
LOG:          add symbol: A.Bar (Var) from line -1
LOG:          error message: B 7:0 Name "Bar" already defined (possibly by an import)
LOG:          After:
LOG:            B.Foo (FuncDef) found
LOG:            A.Bar (Var) found
LOG:            B.var (Var) found
LOG:          complete.
LOG:  Type checking A.
LOG:  Type checking B.
A.py:4: error: Module "B" has no attribute "Foo"
A.py:4: error: Module "B" has no attribute "var"
B.py:7: error: Name "Bar" already defined (possibly by an import)
Found 3 errors in 2 files (checked 2 source files)

I plan to fix my code by creating a placeholder instead of a Var. (edit:) Or perhaps not add the symbol at all, since after this missing import, any further bindings to that name are blocked in the same iteration, and since the module will be deferred, there's another chance to repeat the import. More on this later.

[mrolle45]

Good News!

After solving the basic problem with the order of the input files, there were a few other problems which arose, due to the files being analyzed differently. I've solved all of those problems as well.
Now when I run mypy on my full project, with two different orders of input files, I get exactly the same error messages, although in a different order. I have 1727 errors in 29 files out of 40 source files.

I'm going to look through these messages to see if they reveal other problems that were introduced by the changes I made (and resolve those problems), before I can say I am confident in my changes.

After that, I will be putting together a diff between my version (minus things I added purely for debugging purposes) and the 0.931 release, along with a description of all the changes made. When this is done, I will close this issue and open a new issue with just this information, so that it will be clear to all you readers what I actually report as the problems and what I actually did to solve them.