Implement override-based type inference for instance methods.

pkg/analyzer/lib/src/task/strong/checker.dart

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // TODO(jmesserly): this was ported from package:dev_compiler, and needs to be
 // refactored to fit into analyzer.
 library analyzer.src.task.strong.checker;
 
 import 'package:analyzer/analyzer.dart';
 import 'package:analyzer/dart/ast/ast.dart';
@@ skipping 1271 matching lines @@
     // current class against definitions here and in superclasses.
     var localInterfaces = new Set<InterfaceType>();
     var type = element.type;
     type.interfaces.forEach((i) => find(i, localInterfaces));
     _checkInterfacesOverrides(type, localInterfaces, seen,
         includeParents: true, classNode: node);
 
     // Check also how we override locally the interfaces from parent classes if
     // the parent class is abstract. Otherwise, these will be checked as
     // overrides on the concrete superclass.
+    // We detect superclass circularities using the "tortoise and hare"
+    // algorithm.
     var superInterfaces = new Set<InterfaceType>();
     var parent = type.superclass;
+    var hare = type.superclass?.superclass;
     // TODO(sigmund): we don't seem to be reporting the analyzer error that a
     // non-abstract class is not implementing an interface. See
     // https://github.com/dart-lang/dart-dev-compiler/issues/25
     while (parent != null && parent.element.isAbstract) {
+      if (identical(parent, hare)) break;
       parent.interfaces.forEach((i) => find(i, superInterfaces));
       parent = parent.superclass;
+      hare = hare?.superclass?.superclass;
     }
     _checkInterfacesOverrides(type, superInterfaces, seen,
         includeParents: false, classNode: node);
   }
 
   /// Check that individual methods and fields in [node] correctly override
   /// the declarations in [baseType].
   ///
   /// The [errorLocation] node indicates where errors are reported, see
   /// [_checkSingleOverride] for more details.
@@ skipping 285 matching lines @@
   }
 
   /// If node is a [ClassDeclaration] returns its members, otherwise if node is
   /// a [ClassTypeAlias] this returns an empty list.
   WithClause _withClause(Declaration node) {
     return node is ClassDeclaration
         ? node.withClause
         : (node as ClassTypeAlias).withClause;
   }
 }