Use a mro traversal for finding abstract methods. Closes issue #415.

This patch adds a new unimplemented_abstract_methods in pylint.checkers.utils,
which is used to obtain all the abstract methods which weren't implemented
anywhere in the mro of a class. The code works now by traversing the mro, gathering
all abstract methods encountered at each step and resolving the implemented ones
through either definition or assignment. This disables a couple of false
positives on classes with complex hierarchies.

12 files changed, 299 insertions, 93 deletions

diff --git a/ChangeLog b/ChangeLog
index 6e13e04..cc0ac42 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -14,6 +14,8 @@ ChangeLog for Pylint
     * Proper abstract method lookup while checking for
       abstract-class-instantiated. Closes issue #401.
 
+    * Use a mro traversal for finding abstract methods. Closes issue #415.
+
 
 2014-11-23 -- 1.4.0
 
diff --git a/checkers/base.py b/checkers/base.py
index 60bc096..d363dd7 100644
--- a/checkers/base.py
+++ b/checkers/base.py
@@ -45,6 +45,7 @@ from pylint.checkers.utils import (
     has_known_bases,
     NoSuchArgumentError,
     is_import_error,
+    unimplemented_abstract_methods,
     )
 
 
@@ -148,8 +149,7 @@ if sys.version_info < (3, 0):
     PROPERTY_CLASSES = set(('__builtin__.property', 'abc.abstractproperty'))
 else:
     PROPERTY_CLASSES = set(('builtins.property', 'abc.abstractproperty'))
-ABC_METHODS = set(('abc.abstractproperty', 'abc.abstractmethod',
-                   'abc.abstractclassmethod', 'abc.abstractstaticmethod'))
+
 
 def _determine_function_name_type(node):
     """Determine the name type whose regex the a function's name should match.
@@ -179,55 +179,17 @@ def _determine_function_name_type(node):
             return 'attr'
     return 'method'
 
-def _decorated_with_abc(func):
-    """ Determine if the `func` node is decorated
-    with `abc` decorators (abstractmethod et co.)
-    """
-    if func.decorators:
-        for node in func.decorators.nodes:
-            try:
-                infered = next(node.infer())
-            except InferenceError:
-                continue
-            if infered and infered.qname() in ABC_METHODS:
-                return True
+
 
 def _has_abstract_methods(node):
     """
-    Determine if the given `node` has
-    abstract methods, defined with `abc` module.
+    Determine if the given `node` has abstract methods.
+
+    The methods should be made abstract by decorating them
+    with `abc` decorators.
     """
-    visited = set()
-    try:
-        mro = reversed(node.mro())
-    except NotImplementedError:
-        # Old style class, it will not have a mro.
-        return False
-    for ancestor in mro:
-        for obj in ancestor.values():
-            infered = obj
-            if isinstance(obj, astroid.AssName):
-                infered = safe_infer(obj)
-                if not infered:
-                    continue
-                if not isinstance(infered, astroid.Function):
-                    if obj.name in visited:
-                        visited.remove(obj.name)
-            if isinstance(infered, astroid.Function):
-                # It's critical to use the original name,
-                # since after inferring, an object can be something
-                # else than expected, as in the case of the
-                # following assignment.
-                #
-                # class A:
-                #     def keys(self): pass
-                #     __iter__ = keys
-                abstract = _decorated_with_abc(infered)
-                if abstract:
-                    visited.add(obj.name)
-                elif not abstract and obj.name in visited:
-                    visited.remove(obj.name)
-    return len(visited) > 0
+    return len(unimplemented_abstract_methods(node)) > 0
+
 
 def report_by_type_stats(sect, stats, old_stats):
     """make a report of
diff --git a/checkers/classes.py b/checkers/classes.py
index 030bee6..f7a344e 100644
--- a/checkers/classes.py
+++ b/checkers/classes.py
@@ -30,7 +30,7 @@ from pylint.checkers import BaseChecker
 from pylint.checkers.utils import (
     PYMETHODS, overrides_a_method, check_messages, is_attr_private,
     is_attr_protected, node_frame_class, safe_infer, is_builtin_object,
-    decorated_with_property)
+    decorated_with_property, unimplemented_abstract_methods)
 import six
 
 if sys.version_info >= (3, 0):
@@ -800,21 +800,28 @@ a metaclass class method.'}
         """check that the given class node implements abstract methods from
         base classes
         """
+        def is_abstract(method):
+            return method.is_abstract(pass_is_abstract=False)
+
         # check if this class abstract
         if class_is_abstract(node):
             return
-        for method in node.methods():
+
+        methods = sorted(
+            unimplemented_abstract_methods(node, is_abstract).items(),
+            key=lambda item: item[0],
+        )
+        for name, method in methods:
             owner = method.parent.frame()
             if owner is node:
                 continue
             # owner is not this class, it must be a parent class
             # check that the ancestor's method is not abstract
-            if method.name in node.locals:
+            if name in node.locals:
                 # it is redefined as an attribute or with a descriptor
                 continue
-            if method.is_abstract(pass_is_abstract=False):
-                self.add_message('abstract-method', node=node,
-                                 args=(method.name, owner.name))
+            self.add_message('abstract-method', node=node,
+                             args=(name, owner.name))
 
     def _check_interfaces(self, node):
         """check that the given class node really implements declared
diff --git a/checkers/utils.py b/checkers/utils.py
index f3a7d17..2df59e1 100644
--- a/checkers/utils.py
+++ b/checkers/utils.py
@@ -34,6 +34,8 @@ if not PY3K:
     EXCEPTIONS_MODULE = "exceptions"
 else:
     EXCEPTIONS_MODULE = "builtins"
+ABC_METHODS = set(('abc.abstractproperty', 'abc.abstractmethod',
+                   'abc.abstractclassmethod', 'abc.abstractstaticmethod'))
 
 
 class NoSuchArgumentError(Exception):
@@ -499,3 +501,60 @@ def decorated_with_property(node):
                             return True
         except astroid.InferenceError:
             pass
+
+
+def decorated_with_abc(func):
+    """Determine if the `func` node is decorated with `abc` decorators."""
+    if func.decorators:
+        for node in func.decorators.nodes:
+            try:
+                infered = next(node.infer())
+            except astroid.InferenceError:
+                continue
+            if infered and infered.qname() in ABC_METHODS:
+                return True
+
+
+def unimplemented_abstract_methods(node, is_abstract_cb=decorated_with_abc):
+    """
+    Get the unimplemented abstract methods for the given *node*.
+
+    A method can be considered abstract if the callback *is_abstract_cb*
+    returns a ``True`` value. The check defaults to verifying that
+    a method is decorated with abstract methods.
+    The function will work only for new-style classes. For old-style
+    classes, it will simply return an empty dictionary.
+    For the rest of them, it will return a dictionary of abstract method
+    names and their inferred objects.
+    """
+    visited = {}
+    try:
+        mro = reversed(node.mro())
+    except NotImplementedError:
+        # Old style class, it will not have a mro.
+        return {}
+    for ancestor in mro:
+        for obj in ancestor.values():
+            infered = obj
+            if isinstance(obj, astroid.AssName):
+                infered = safe_infer(obj)
+                if not infered:
+                    continue
+                if not isinstance(infered, astroid.Function):
+                    if obj.name in visited:
+                        del visited[obj.name]
+            if isinstance(infered, astroid.Function):
+                # It's critical to use the original name,
+                # since after inferring, an object can be something
+                # else than expected, as in the case of the
+                # following assignment.
+                #
+                # class A:
+                #     def keys(self): pass
+                #     __iter__ = keys
+                abstract = is_abstract_cb(infered)
+                if abstract:
+                    visited[obj.name] = infered
+                elif not abstract and obj.name in visited:
+                    del visited[obj.name]
+    return visited
diff --git a/test/functional/abstract_method_py2.py b/test/functional/abstract_method_py2.py
new file mode 100644
index 0000000..d71faba
--- /dev/null
+++ b/test/functional/abstract_method_py2.py
@@ -0,0 +1,91 @@
+"""Test abstract-method warning."""
+from __future__ import print_function
+
+# pylint: disable=missing-docstring, no-init, no-self-use
+# pylint: disable=too-few-public-methods
+# pylint: disable=abstract-class-little-used, abstract-class-not-used
+import abc
+
+class Abstract(object):
+    def aaaa(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+    def bbbb(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+
+class AbstractB(Abstract):
+    """Abstract class.
+
+    this class is checking that it does not output an error msg for
+    unimplemeted methods in abstract classes
+    """
+    def cccc(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+class Concret(Abstract): # [abstract-method]
+    """Concrete class"""
+
+    def aaaa(self):
+        """overidden form Abstract"""
+
+
+class Structure(object):
+    __metaclass__ = abc.ABCMeta
+
+    @abc.abstractmethod
+    def __iter__(self):
+        pass
+    @abc.abstractmethod
+    def __len__(self):
+        pass
+    @abc.abstractmethod
+    def __contains__(self):
+        pass
+    @abc.abstractmethod
+    def __hash__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Container(Structure):
+    def __contains__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Sizable(Structure):
+    def __len__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Hashable(Structure):
+    __hash__ = 42
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Iterator(Structure):
+    def keys(self):
+        return iter([1, 2, 3])
+
+    __iter__ = keys
+
+
+class AbstractSizable(Structure):
+    @abc.abstractmethod
+    def length(self):
+        pass
+    __len__ = length
+
+
+class GoodComplexMRO(Container, Iterator, Sizable, Hashable):
+    pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class BadComplexMro(Container, Iterator, AbstractSizable):
+    pass
diff --git a/test/functional/abstract_method_py2.rc b/test/functional/abstract_method_py2.rc
new file mode 100644
index 0000000..b11e16d
--- /dev/null
+++ b/test/functional/abstract_method_py2.rc
@@ -0,0 +1,2 @@
+[testoptions]
+max_pyver=3.0
\ No newline at end of file
diff --git a/test/functional/abstract_method_py2.txt b/test/functional/abstract_method_py2.txt
new file mode 100644
index 0000000..4ccf9ca
--- /dev/null
+++ b/test/functional/abstract_method_py2.txt
@@ -0,0 +1,16 @@
+abstract-method:29:Concret:"Method 'bbbb' is abstract in class 'Abstract' but is not overridden"

+abstract-method:54:Container:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:54:Container:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:54:Container:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:60:Sizable:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:60:Sizable:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:60:Sizable:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:66:Hashable:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:66:Hashable:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:66:Hashable:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:71:Iterator:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:71:Iterator:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:71:Iterator:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:90:BadComplexMro:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:90:BadComplexMro:"Method '__len__' is abstract in class 'AbstractSizable' but is not overridden"

+abstract-method:90:BadComplexMro:"Method 'length' is abstract in class 'AbstractSizable' but is not overridden"

diff --git a/test/functional/abstract_method_py3.py b/test/functional/abstract_method_py3.py
new file mode 100644
index 0000000..308a6e5
--- /dev/null
+++ b/test/functional/abstract_method_py3.py
@@ -0,0 +1,89 @@
+"""Test abstract-method warning."""
+from __future__ import print_function
+
+# pylint: disable=missing-docstring, no-init, no-self-use
+# pylint: disable=too-few-public-methods
+# pylint: disable=abstract-class-little-used, abstract-class-not-used
+import abc
+
+class Abstract(object):
+    def aaaa(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+    def bbbb(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+
+class AbstractB(Abstract):
+    """Abstract class.
+
+    this class is checking that it does not output an error msg for
+    unimplemeted methods in abstract classes
+    """
+    def cccc(self):
+        """should be overridden in concrete class"""
+        raise NotImplementedError()
+
+class Concret(Abstract): # [abstract-method]
+    """Concrete class"""
+
+    def aaaa(self):
+        """overidden form Abstract"""
+
+
+class Structure(object, metaclass=abc.ABCMeta):
+    @abc.abstractmethod
+    def __iter__(self):
+        pass
+    @abc.abstractmethod
+    def __len__(self):
+        pass
+    @abc.abstractmethod
+    def __contains__(self):
+        pass
+    @abc.abstractmethod
+    def __hash__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Container(Structure):
+    def __contains__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Sizable(Structure):
+    def __len__(self):
+        pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Hashable(Structure):
+    __hash__ = 42
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class Iterator(Structure):
+    def keys(self):
+        return iter([1, 2, 3])
+
+    __iter__ = keys
+
+
+class AbstractSizable(Structure):
+    @abc.abstractmethod
+    def length(self):
+        pass
+    __len__ = length
+
+
+class GoodComplexMRO(Container, Iterator, Sizable, Hashable):
+    pass
+
+
+# +1: [abstract-method, abstract-method, abstract-method]
+class BadComplexMro(Container, Iterator, AbstractSizable):
+    pass
diff --git a/test/functional/abstract_method_py3.rc b/test/functional/abstract_method_py3.rc
new file mode 100644
index 0000000..a2ab06c
--- /dev/null
+++ b/test/functional/abstract_method_py3.rc
@@ -0,0 +1,2 @@
+[testoptions]
+min_pyver=3.0
\ No newline at end of file
diff --git a/test/functional/abstract_method_py3.txt b/test/functional/abstract_method_py3.txt
new file mode 100644
index 0000000..fd01e9a
--- /dev/null
+++ b/test/functional/abstract_method_py3.txt
@@ -0,0 +1,16 @@
+abstract-method:29:Concret:"Method 'bbbb' is abstract in class 'Abstract' but is not overridden"

+abstract-method:52:Container:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:52:Container:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:52:Container:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:58:Sizable:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:58:Sizable:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:58:Sizable:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:64:Hashable:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:64:Hashable:"Method '__iter__' is abstract in class 'Structure' but is not overridden"

+abstract-method:64:Hashable:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:69:Iterator:"Method '__contains__' is abstract in class 'Structure' but is not overridden"

+abstract-method:69:Iterator:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:69:Iterator:"Method '__len__' is abstract in class 'Structure' but is not overridden"

+abstract-method:88:BadComplexMro:"Method '__hash__' is abstract in class 'Structure' but is not overridden"

+abstract-method:88:BadComplexMro:"Method '__len__' is abstract in class 'AbstractSizable' but is not overridden"

+abstract-method:88:BadComplexMro:"Method 'length' is abstract in class 'AbstractSizable' but is not overridden"

diff --git a/test/input/func_w0223.py b/test/input/func_w0223.py
deleted file mode 100644
index 5d380cc..0000000
--- a/test/input/func_w0223.py
+++ /dev/null
@@ -1,36 +0,0 @@
-# pylint: disable=R0903,R0922
-"""test overriding of abstract method
-"""
-from __future__ import print_function
-__revision__ = '$Id: func_w0223.py,v 1.2 2004-09-29 08:35:13 syt Exp $'
-
-class Abstract(object):
-    """abstract class
-    """
-    def aaaa(self):
-        """should be overridden in concrete class"""
-        raise NotImplementedError()
-
-
-    def bbbb(self):
-        """should be overridden in concrete class"""
-        raise NotImplementedError()
-
-    def __init__(self):
-        pass
-
-class AbstractB(Abstract):
-    """abstract class
-    this class is checking that it does not output an error msg for
-    unimplemeted methods in abstract classes
-    """
-    def cccc(self):
-        """should be overridden in concrete class"""
-        raise NotImplementedError()
-
-class Concret(Abstract):
-    """concret class"""
-
-    def aaaa(self):
-        """overidden form Abstract"""
-        print(self)
diff --git a/test/messages/func_w0223.txt b/test/messages/func_w0223.txt
deleted file mode 100644
index 943cf03..0000000
--- a/test/messages/func_w0223.txt
+++ /dev/null
@@ -1,4 +0,0 @@
-R: 22:AbstractB: Abstract class not referenced
-W: 31:Concret: Method 'bbbb' is abstract in class 'Abstract' but is not overridden
-
-