py3: defining __eq__ breaks inheritance of __hash__

[chapoton]

This is potentially a large-scale problem, as can be seen using

grep -L "def __hash__" $(git grep -l "def __eq__" ) 

TODO LIST (extracted from errors on sage/python3 testsuite):

Ticket	Module	Notes
#25935	AbelianGroupWithValues_class_with_category	group
#25935	AbelianGroup_class_with_category	group
#?????	AlternatingGroup_with_category	group
#26058	BruhatTitsHarmonicCocycles_with_category
#?????	CartesianProduct_with_category.element_class
#25940	ChainComplex_class_with_category
#?????	ClassGroup_with_category	group
#?????	CompositeConstructionFunctor?
#26061	CrystalOfAlcovePaths_with_category.element_class
#26087	CycleIndexSeriesRing_class_with_category
#?????	CyclicPermutationGroup_with_category	group
#?????	DiCyclicGroup_with_category	group
#?????	DihedralGroup_with_category	group
#?????	EisensteinExtensionFieldCappedRelative_with_category
#?????	EisensteinExtensionRingCappedAbsolute_with_category
#?????	EisensteinExtensionRingCappedRelative_with_category
#?????	EisensteinExtensionRingFixedMod_with_category
#?????	FiniteWord_list
#?????	FiniteWord_str
#?????	FiniteWord_tuple
#?????	Gamma0_class_with_category	group
#?????	Gamma1_class_with_category	group
#?????	GammaH_class_with_category	group
#?????	Gamma_class_with_category	group
#26063	HammingCode_with_category
#25946	HyperellipticCurve_g2_padic_field_with_category
#25946	HyperellipticCurve_g2_rational_field_with_category
#25946	HyperellipticCurve_padic_field_with_category
#25946	HyperellipticCurve_rational_field_with_category
#?????	IdealMonoid_c_with_category
#?????	InfinitePolynomialFunctor?
#?????	KleinFourGroup_with_category	group
#?????	LabelledBinaryTrees_with_category.element_class
#?????	MPolynomial_polydict
#?????	MathieuGroup_with_category	group
#?????	ModularSymbolsAmbient_wtk_eps_with_category
#?????	MultivariateProduct_with_category.element_class
#?????	NCPolynomialIdeal
#?????	PGL_with_category	group
#?????	PSL_with_category	group
#?????	Partitions_with_constraints_with_category
#?????	PolynomialQuotientRing_domain_with_category
#?????	PolynomialQuotientRing_field_with_category
#?????	PolynomialQuotientRing_generic_with_category
#?????	PrimitiveGroup_with_category	group
#?????	ProjectiveSpace_rational_field_with_category
#?????	ProjectiveSpace_ring_with_category
#?????	QuaternionFractionalIdeal_rational
#?????	QuaternionGroup_with_category	group
#?????	SL2Z_class_with_category	group
#26062	ShiftedPrimedTableaux_shape_with_category.element_class
#?????	SimplicialSetMorphism?
#?????	SmoothCharacterGroupQp_with_category	group
#?????	SmoothCharacterGroupRamifiedQuadratic_with_category	group
#?????	SmoothCharacterGroupUnramifiedQuadratic_with_category	group
#?????	SubsetsSorted_with_category
#?????	Subsets_sk_with_category
#26064	SymbolicConstantsSubring_with_category
#?????	SymmetricGroup_with_category	group
#?????	TransitiveGroup_with_category	group
#?????	UnivariateProduct_with_category.element_class
#?????	UnramifiedExtensionFieldCappedRelative_with_category
#?????	UnramifiedExtensionRingCappedAbsolute_with_category
#?????	UnramifiedExtensionRingCappedRelative_with_category
#?????	UnramifiedExtensionRingFixedMod_with_category
#26058	pAdicAutomorphicForms_with_category
#?????	sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement

[jdemeyer]

Good to know is that there is a metaclass InheritComparison which is supposed to fix that problem.

[embray]

I've also, at least, provisionally, implemented __hash__'s for a lot of classes. I haven't pushed any of those changes yet because I've been lazy about adding docstrings for them and need to do that.

There are also lots of cases where it's fine to just assign __hash__ = BaseClass.__hash__ (in fact this is the case for all classes). That said, the default __hash__ a lot of classes have is not very good, or sometimes problematic (e.g. I think some object are hashable even though they're not immutable). So it's a good opportunity to check those on a case base case basis.

[chapoton]

ok. But anyway, this seems to require a lot of work..

I did a few simple cases in #24552

[embray]

Of the commits in my python 3 branch that I haven't made tickets for yet, I've added __hash__ implementations in at least the following (and maybe more):

src/sage/algebras/free_algebra.py
src/sage/algebras/free_algebra_quotient.py
src/sage/algebras/quatalg/quaternion_algebra.py
src/sage/algebras/steenrod/steenrod_algebra.py
src/sage/categories/pushout.py
src/sage/coding/hamming_code.py
src/sage/coding/linear_code.py
src/sage/combinat/crystals/generalized_young_walls.py
src/sage/combinat/integer_vector.py
src/sage/combinat/rigged_configurations/rigged_partition.py
src/sage/combinat/root_system/type_dual.py
src/sage/combinat/species/series.py
src/sage/combinat/subset.py
src/sage/combinat/subword_complex.py
src/sage/combinat/words/word_datatypes.pyx
src/sage/groups/abelian_gps/abelian_group.py
src/sage/groups/perm_gps/permgroup_named.py
src/sage/homology/chain_complex.py
src/sage/homology/chain_complex_morphism.py
src/sage/manifolds/continuous_map.py
src/sage/modular/arithgroup/congroup_generic.py
src/sage/modular/modsym/ambient.py
src/sage/monoids/free_monoid.py
src/sage/rings/fraction_field.py
src/sage/rings/ideal_monoid.py
src/sage/rings/number_field/order.py
src/sage/rings/padics/padic_extension_generic.py
src/sage/rings/polynomial/laurent_polynomial_ring.py
src/sage/rings/polynomial/polynomial_quotient_ring.py
src/sage/structure/element_wrapper.pyx

[tscrim]

src/sage/combinat/rigged_configurations/bij_abstract_class.py

and its subclasses should never be used in a hash (it is a helper class to perform a bijection) and the __eq__ is just there so the TestSuite with the pickling passes. Probably the better thing to do here is to remove the __eq__ and skip the pickling test (this is some of the first code I contributed to Sage, memories...).

[embray]

Quick question one of you can maybe answer: If a class inherits from UniqueRepresentation, then should it even be implementing __eq__? ISTM it should just use the __eq__ implementation inherited from UniqueRepresentation (via WithEqualityById).

I've found several classes that inherit from UniqueRepresentation but that still implement their own __eq__ like:

def __eq__(self, other):
    return isinstance(other, type(self)) and self.foo == other.foo and self.bar == other.bar

for some list of various attributes of the objects that are mostly determined at the object's construction.

I admit I don't fully understand yet how UniqueRepresentation is supposed to work though (I will read the docs for it carefully now). But it seems like it should implicitly cover this use case (and thus eliminate the need for a lot of explicit __eq__ and hence __hash__ implementations).

[embray]

Or could it be that in some of these cases their __eq__ is defined more broadly than just equality by identity? I admit in some of these cases I don't know the mathematical background well enough to determine this, and the given examples don't always make the intent clear either.

[embray]

Okay, quoting the docs:

Instances of a class have a unique instance behavior when instances of this class evaluate equal if and only if they are identical.

So IIUC, a class really shouldn't be inheriting UniqueRepresentation unless they truly do define equality by identity. So either these classes shouldn't be defining __eq__, or they aren't using UniqueRepresentation appropriately (and should perhaps just be using CachedRepresentation at the most).

[jdemeyer]

Replying to embray:

So IIUC, a class really shouldn't be inheriting UniqueRepresentation unless they truly do define equality by identity. So either these classes shouldn't be defining __eq__, or they aren't using UniqueRepresentation appropriately (and should perhaps just be using CachedRepresentation at the most).

That sounds reasonable.

[embray]

I'm just going through sage.algebras and finding several cases like this (this is where I started since that's where I was recently toiling on the __hash__ issue). Indeed, it seems many of these classes predate, and/or have __eq__ methods that predate UniqueRepresentation.

[embray]

Another angle to this that Jeroen has already pointed out a couple times is that there is InheritComparison. This could be extended to also automatically force the inheritance of __hash__. I think that would solve a lot of this "for free". But what I've also found is that this has exposed many cases where class's default inherited __hash__es are not well-defined w.r.t. their __eq__, or other issues like in #25387.

In other words, I think that the new behavior in Python 3, while annoying in terms of how much it breaks in Sage, is good that it forces us to think more carefully about this. So I'd be hesitant to resort to such a brute-force fix except as a last resort.

[egourgoulhon]

Among the files listed in the ticket description, the case

src/sage/manifolds/continuous_map.py

is dealt with by #25502. The other manifold cases:

src/sage/manifolds/chart.py
src/sage/manifolds/chart_func.py
src/sage/manifolds/differentiable/affine_connection.py
src/sage/manifolds/differentiable/tensorfield.py
src/sage/manifolds/scalarfield.py

should trigger no Python3 issue since none of these classes is intended to be hashable. Same thing for

src/sage/tensor/modules/comp.py
src/sage/tensor/modules/free_module_morphism.py
src/sage/tensor/modules/free_module_tensor.py
src/sage/tensor/modules/tensor_with_indices.py

[chapoton]

see #25586 and #25587 for some partial cure

[chapoton]

some failures in sage3 doctests:

 'TypeError("unhashable type: \'AbsoluteOrder_with_category\'",)',
 'TypeError("unhashable type: \'RelativeOrder_with_category\'",)',
 "TypeError: unhashable type: 'AbelianGroup_class_with_category'",
 "TypeError: unhashable type: 'AbsoluteOrder_with_category'",
 "TypeError: unhashable type: 'CartanType_affine_with_superclass'",
 "TypeError: unhashable type: 'CartesianProduct_with_category.element_class'",
 "TypeError: unhashable type: 'ChainComplex_class_with_category'",
 "TypeError: unhashable type: 'ClassGroup_with_category'",
 "TypeError: unhashable type: 'CompositeConstructionFunctor'",
 "TypeError: unhashable type: 'CrystalOfAlcovePaths_with_category.element_class'",
 "TypeError: unhashable type: 'CycleIndexSeriesRing_class_with_category'",
 "TypeError: unhashable type: 'CyclicPermutationGroup_with_category'",
 "TypeError: unhashable type: 'DihedralGroup_with_category'",
 "TypeError: unhashable type: 'EisensteinExtensionFieldCappedRelative_with_category'",
 "TypeError: unhashable type: 'EisensteinExtensionRingCappedAbsolute_with_category'",
 "TypeError: unhashable type: 'EisensteinExtensionRingCappedRelative_with_category'",
 "TypeError: unhashable type: 'EisensteinExtensionRingFixedMod_with_category'",
 "TypeError: unhashable type: 'FpT_with_category'",
 "TypeError: unhashable type: 'FractionField_1poly_field_with_category'",
 "TypeError: unhashable type: 'FractionField_generic_with_category'",
 "TypeError: unhashable type: 'Gamma0_class_with_category'",
 "TypeError: unhashable type: 'Gamma1_class_with_category'",
 "TypeError: unhashable type: 'GammaH_class_with_category'",
 "TypeError: unhashable type: 'HammingCode_with_category'",
 "TypeError: unhashable type: 'HyperbolicModelPD_with_category.element_class'",
 "TypeError: unhashable type: 'HyperellipticCurve_g2_rational_field_with_category'",
 "TypeError: unhashable type: 'HyperellipticCurve_rational_field_with_category'",
 "TypeError: unhashable type: 'IdealMonoid_c_with_category'",
 "TypeError: unhashable type: 'InfinitePolynomialFunctor'",
 "TypeError: unhashable type: 'KleinFourGroup_with_category'",
 "TypeError: unhashable type: 'LabelledBinaryTrees_with_category.element_class'",
 "TypeError: unhashable type: 'LaurentPolynomialRing_mpair_with_category'",
 "TypeError: unhashable type: 'LaurentPolynomialRing_univariate_with_category'",
 "TypeError: unhashable type: 'MPolynomialRing_polydict_domain_with_category'",
 "TypeError: unhashable type: 'MPolynomialRing_polydict_with_category'",
 "TypeError: unhashable type: 'MPolynomial_polydict'",
 "TypeError: unhashable type: 'ModularSymbolsAmbient_wtk_eps_with_category'",
 "TypeError: unhashable type: 'MultivariateProduct_with_category.element_class'",
 "TypeError: unhashable type: 'OverconvergentModularFormsSpace_with_category'",
 "TypeError: unhashable type: 'Partitions_with_constraints_with_category'",
 "TypeError: unhashable type: 'PolynomialQuotientRing_field_with_category'",
 "TypeError: unhashable type: 'PolynomialQuotientRing_generic_with_category'",
 "TypeError: unhashable type: 'ProjectiveSpace_rational_field_with_category'",
 "TypeError: unhashable type: 'QuaternionAlgebra_ab_with_category'",
 "TypeError: unhashable type: 'QuaternionFractionalIdeal_rational'",
 "TypeError: unhashable type: 'RelativeOrder_with_category'",
 "TypeError: unhashable type: 'SL2Z_class_with_category'",
 "TypeError: unhashable type: 'Subsets_sk_with_category'",
 "TypeError: unhashable type: 'SymbolicConstantsSubring_with_category'",
 "TypeError: unhashable type: 'SymmetricGroup_with_category'",
 "TypeError: unhashable type: 'ToricVariety_field_with_category'",
 "TypeError: unhashable type: 'UnivariateProduct_with_category.element_class'",
 "TypeError: unhashable type: 'UnramifiedExtensionFieldCappedRelative_with_category'",
 "TypeError: unhashable type: 'UnramifiedExtensionRingCappedAbsolute_with_category'",
 "TypeError: unhashable type: 'UnramifiedExtensionRingCappedRelative_with_category'",
 "TypeError: unhashable type: 'UnramifiedExtensionRingFixedMod_with_category'",
 "TypeError: unhashable type: 'pAdicAutomorphicForms_with_category'",
 "TypeError: unhashable type: 'sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement'"]

[jhpalmieri]

Note that the changes (taken from comment:2)

src/sage/groups/abelian_gps/abelian_group.py

@@ -553 +553 @@
             cat = cat.Infinite()
         AbelianGroupBase.__init__(self, category=cat)
 
+    __hash__ = UniqueRepresentation.__hash__
+
     def is_isomorphic(left, right):
         """
         Check whether ``left`` and ``right`` are isomorphic

src/sage/groups/perm_gps/permgroup_named.py

@@ -149 +149 @@
         """
         return super(CachedRepresentation, self).__eq__(other)
 
+    __hash__ = CachedRepresentation.__hash__
+
 
 class PermutationGroup_symalt(PermutationGroup_unique):
     """

fix many Python 3 doctest failures in sage/homology. I don't know if this is the correct approach, or perhaps there is something more systematic to make hashes inherit even when __eq__ is defined.

[jdemeyer]

If you're using the __hash__ of UniqueRepresentation but not its __eq__, then you're doing it wrong. So this might indicate an actual bug.

[jhpalmieri]

That class has the line

    __eq__ = is_isomorphic

so that generator names (for example) don't affect equality. (is_isomorphic just checks whether the elementary divisors match up.) We could define __hash__ correspondingly. For the simplicial complex code, the important thing (I think) is that the class of abelian groups is hashable. I assume that any reasonable hash function will work.

(I also don't know how or why the design decisions for AbelianGroup_class were made.)

[jhpalmieri]

Confirmed:

src/sage/groups/abelian_gps/abelian_group.py

@@ -553 +553 @@
             cat = cat.Infinite()
         AbelianGroupBase.__init__(self, category=cat)
 
+    def __hash__(self):
+        return hash(self.elementary_divisors())
+
     def is_isomorphic(left, right):
         """
         Check whether ``left`` and ``right`` are isomorphic

works just as well, at least as far as the homology code is concerned.

[jdemeyer]

Replying to jhpalmieri:

That class has the line

    __eq__ = is_isomorphic

so that generator names (for example) don't affect equality.

This is different from most other things in Sage though. For example

sage: GF(9, 'a') == GF(9, 'b')
False
sage: QQ['x'] == QQ['y']
False

I'm not saying that this is necessarily a bug. However, if you can change __eq__ without breaking anything else, I would do that instead of changing __hash__.

[jdemeyer]

I opened #25935 for AbelianGroup_class. Please continue the discussion there.

[jhpalmieri]

I opened #25940 for ChainComplex_class.

[embray]

Added one for HyperellipticCurve_generic in #25946.