Why/When in Python does `x==y` call `y.__eq__(x)`?

You're missing a key exception to the usual behaviour: when the right-hand operand is an instance of a subclass of the class of the left-hand operand, the special method for the right-hand operand is called first.

See the documentation at:

http://docs.python.org/reference/datamodel.html#coercion-rules

and in particular, the following two paragraphs:

For objects x and y, first x.__op__(y) is tried. If this is not implemented or returns NotImplemented, y.__rop__(x) is tried. If this is also not implemented or returns NotImplemented, a TypeError exception is raised. But see the following exception:

Exception to the previous item: if the left operand is an instance of a built-in type or a new-style class, and the right operand is an instance of a proper subclass of that type or class and overrides the base’s __rop__() method, the right operand’s __rop__() method is tried before the left operand’s __op__() method.

Actually, in the docs, it states:

[__cmp__ is c]alled by comparison operations if rich comparison (see above) is not defined.

__eq__ is a rich comparison method and, in the case of TestCmp, is not defined, hence the calling of __cmp__

As I know, __eq__() is a so-called “rich comparison” method, and is called for comparison operators in preference to __cmp__() below. __cmp__() is called if "rich comparison" is not defined.

So in A == B:
If __eq__() is defined in A it will be called
Else __cmp__() will be called

__eq__() defined in 'str' so your __cmp__() function was not called.

The same rule is for __ne__(), __gt__(), __ge__(), __lt__() and __le__() "rich comparison" methods.