New semantic analyzer: remove the limit on max number of iterations (#6499)

JukkaL · web-flow · commit 9d335e209b76 · 2019-03-01T18:41:46.000Z
Keep track of added names. If an iteration didn't add anything new, any further work is meaningless and the next iteration will be the last one. Avoid infinite loops by failing if the final iterations defers anything. Fixes #6485.
diff --git a/mypy/newsemanal/semanal.py b/mypy/newsemanal/semanal.py
@@ -214,7 +214,13 @@ class NewSemanticAnalyzer(NodeVisitor[None],
     # Stack of functions being analyzed
     function_stack = None  # type: List[FuncItem]
 
-    # Is this the final iteration of semantic analysis?
+    # Set to True if semantic analysis defines a name, or replaces a
+    # placeholder definition. If some iteration makes no progress,
+    # there can be at most one additional final iteration (see below).
+    progress = False
+
+    # Is this the final iteration of semantic analysis (where we report
+    # unbound names due to cyclic definitions)?
     _final_iteration = False
 
     loop_depth = 0         # Depth of breakable loops
@@ -307,6 +313,11 @@ def add_implicit_module_attrs(self, file_node: MypyFile) -> None:
                 assert t is not None, 'type should be specified for {}'.format(name)
                 typ = UnboundType(t)
 
+            existing = file_node.names.get(name)
+            if existing is not None and not isinstance(existing.node, PlaceholderNode):
+                # Already exists.
+                continue
+
             an_type = self.anal_type(typ)
             if an_type:
                 var = Var(name, an_type)
@@ -4052,15 +4063,23 @@ def add_symbol_table_node(self, name: str, symbol: SymbolTableNode,
         existing = names.get(name)
         if (existing is not None
                 and context is not None
-                and not isinstance(existing.node, PlaceholderNode)):
-            if existing.node != symbol.node:
+                and (not isinstance(existing.node, PlaceholderNode)
+                     or isinstance(symbol.node, PlaceholderNode))):
+            # There is an existing node, so this may be a redefinition.
+            # If the new node points to the same node as the old one,
+            # or if both old and new nodes are placeholders, we don't
+            # need to do anything.
+            if (existing.node != symbol.node
+                    and not (isinstance(existing.node, PlaceholderNode)
+                             and isinstance(symbol.node, PlaceholderNode))):
                 if isinstance(symbol.node, (FuncDef, Decorator)):
                     self.add_func_redefinition(names, name, symbol)
                 if not (isinstance(symbol.node, (FuncDef, Decorator))
                         and self.set_original_def(existing.node, symbol.node)):
                     self.name_already_defined(name, context, existing)
         elif name not in self.missing_names and '*' not in self.missing_names:
             names[name] = symbol
+            self.progress = True
             return True
         return False
 
@@ -4261,6 +4280,11 @@ def lookup_current_scope(self, name: str) -> Optional[SymbolTableNode]:
     def schedule_patch(self, priority: int, patch: Callable[[], None]) -> None:
         self.patches.append((priority, patch))
 
+    def report_hang(self) -> None:
+        self.errors.report(-1, -1,
+                           'Internal error: maximum semantic analysis iteration count reached',
+                           blocker=True)
+
 
 def replace_implicit_first_type(sig: FunctionLike, new: Type) -> FunctionLike:
     if isinstance(sig, CallableType):
diff --git a/mypy/newsemanal/semanal_main.py b/mypy/newsemanal/semanal_main.py
@@ -47,8 +47,9 @@
 Patches = List[Tuple[int, Callable[[], None]]]
 
 
-# Perform up to this many semantic analysis iterations until giving up trying to bind all names.
-MAX_ITERATIONS = 10
+# If we perform this many iterations, raise an exception since we are likely stuck.
+MAX_ITERATIONS = 20
+
 
 # Number of passes over core modules before going on to the rest of the builtin SCC.
 CORE_WARMUP = 2
@@ -132,29 +133,37 @@ def process_top_levels(graph: 'Graph', scc: List[str], patches: Patches) -> None
     # named tuples in builtin SCC.
     if all(m in worklist for m in core_modules):
         worklist += list(reversed(core_modules)) * CORE_WARMUP
-    iteration = 0
     final_iteration = False
+    iteration = 0
     while worklist:
         iteration += 1
-        if iteration == MAX_ITERATIONS:
-            # Give up. Likely it's impossible to bind all names.
+        if iteration > MAX_ITERATIONS:
+            state.manager.new_semantic_analyzer.report_hang()
+            break
+        if final_iteration:
+            # Give up. It's impossible to bind all names.
             state.manager.incomplete_namespaces.clear()
-            final_iteration = True
-        elif iteration > MAX_ITERATIONS:
-            assert False, 'Max iteration count reached in semantic analysis'
         all_deferred = []  # type: List[str]
+        any_progress = False
         while worklist:
             next_id = worklist.pop()
             state = graph[next_id]
             assert state.tree is not None
-            deferred, incomplete = semantic_analyze_target(next_id, state, state.tree, None,
-                                                           final_iteration, patches)
+            deferred, incomplete, progress = semantic_analyze_target(next_id, state,
+                                                                     state.tree,
+                                                                     None,
+                                                                     final_iteration,
+                                                                     patches)
             all_deferred += deferred
+            any_progress = any_progress or progress
             if not incomplete:
                 state.manager.incomplete_namespaces.discard(next_id)
+        if final_iteration:
+            assert not all_deferred, 'Must not defer during final iteration'
         # Reverse to process the targets in the same order on every iteration. This avoids
         # processing the same target twice in a row, which is inefficient.
         worklist = list(reversed(all_deferred))
+        final_iteration = not any_progress
 
 
 def process_functions(graph: 'Graph', scc: List[str], patches: Patches) -> None:
@@ -187,21 +196,28 @@ def process_top_level_function(analyzer: 'NewSemanticAnalyzer',
     Process the body of the function (including nested functions) again and again,
     until all names have been resolved (ot iteration limit reached).
     """
-    iteration = 0
     # We need one more iteration after incomplete is False (e.g. to report errors, if any).
-    more_iterations = incomplete = True
+    final_iteration = False
+    incomplete = True
     # Start in the incomplete state (no missing names will be reported on first pass).
     # Note that we use module name, since functions don't create qualified names.
     deferred = [module]
     analyzer.incomplete_namespaces.add(module)
-    while deferred and more_iterations:
+    iteration = 0
+    while deferred:
         iteration += 1
-        if not (deferred or incomplete) or iteration == MAX_ITERATIONS:
+        if iteration == MAX_ITERATIONS:
+            analyzer.report_hang()
+            break
+        if not (deferred or incomplete) or final_iteration:
             # OK, this is one last pass, now missing names will be reported.
-            more_iterations = False
             analyzer.incomplete_namespaces.discard(module)
-        deferred, incomplete = semantic_analyze_target(target, state, node, active_type,
-                                                       not more_iterations, patches)
+        deferred, incomplete, progress = semantic_analyze_target(target, state, node, active_type,
+                                                                 final_iteration, patches)
+        if final_iteration:
+            assert not deferred, 'Must not defer during final iteration'
+        if not progress:
+            final_iteration = True
 
     analyzer.incomplete_namespaces.discard(module)
     # After semantic analysis is done, discard local namespaces
@@ -226,14 +242,22 @@ def semantic_analyze_target(target: str,
                             node: Union[MypyFile, FuncDef, OverloadedFuncDef, Decorator],
                             active_type: Optional[TypeInfo],
                             final_iteration: bool,
-                            patches: Patches) -> Tuple[List[str], bool]:
+                            patches: Patches) -> Tuple[List[str], bool, bool]:
+    """Semantically analyze a single target.
+
+    Return tuple with these items:
+    - list of deferred targets
+    - was some definition incomplete
+    - were any new names were defined (or placeholders replaced)
+    """
     tree = state.tree
     assert tree is not None
     analyzer = state.manager.new_semantic_analyzer
     # TODO: Move initialization to somewhere else
     analyzer.global_decls = [set()]
     analyzer.nonlocal_decls = [set()]
     analyzer.globals = tree.names
+    analyzer.progress = False
     with state.wrap_context(check_blockers=False):
         with analyzer.file_context(file_node=tree,
                                    fnam=tree.path,
@@ -247,9 +271,9 @@ def semantic_analyze_target(target: str,
             if isinstance(node, Decorator):
                 infer_decorator_signature_if_simple(node, analyzer)
     if analyzer.deferred:
-        return [target], analyzer.incomplete
+        return [target], analyzer.incomplete, analyzer.progress
     else:
-        return [], analyzer.incomplete
+        return [], analyzer.incomplete, analyzer.progress
 
 
 def check_type_arguments(graph: 'Graph', scc: List[str], errors: Errors) -> None:
