py3: defining __eq__ breaks inheritance of __hash__

[fchapoton]

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
#26162	AlternatingGroup_with_category	group
#26058	BruhatTitsHarmonicCocycles_with_category
#26145	CartesianProduct_with_category.element_class	product
#25940	ChainComplex_class_with_category
#25935	ClassGroup_with_category	group
#26192	CompositeConstructionFunctor	functor
#26061	CrystalOfAlcovePaths_with_category.element_class
#26087	CycleIndexSeriesRing_class_with_category
#26162	CyclicPermutationGroup_with_category	group
#26162	DiCyclicGroup_with_category	group
#26162	DihedralGroup_with_category	group
#26088	EisensteinExtensionFieldCappedRelative_with_category
#26088	EisensteinExtensionRingCappedAbsolute_with_category
#26088	EisensteinExtensionRingCappedRelative_with_category
#26088	EisensteinExtensionRingFixedMod_with_category
#26179	FiniteWord_list
#26179	FiniteWord_str
#26179	FiniteWord_tuple
#26167	Gamma0_class_with_category	group
#26167	Gamma1_class_with_category	group
#26167	GammaH_class_with_category	group
#26167	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
#26094	IdealMonoid_c_with_category	ideal, maybe fixed in #26094
#26192	InfinitePolynomialFunctor	functor
#26162	KleinFourGroup_with_category	group
#26162	MathieuGroup_with_category	group
#26093	ModularSymbolsAmbient_wtk_eps_with_category
#26145	MultivariateProduct_with_category.element_class	product
#26094	NCPolynomialIdeal	ideal
#26162	PGL_with_category	group
#26162	PSL_with_category	group
#26158	Partitions_with_constraints_with_category
#26165	PolynomialQuotientRing_domain_with_category
#26165	PolynomialQuotientRing_field_with_category
#26165	PolynomialQuotientRing_generic_with_category
	PrimitiveGroup_with_category	fixed somewhere in 8.4.b4
#26163	QuaternionFractionalIdeal_rational	ideal
#26162	QuaternionGroup_with_category	group
#26167	SL2Z_class_with_category	group
#26062	ShiftedPrimedTableaux_shape_with_category.element_class
	SimplicialSetMorphism	Fixed somewhere in 8.4.b3
#26089	SmoothCharacterGroupQp_with_category	group
#26089	SmoothCharacterGroupRamifiedQuadratic_with_category	group
#26089	SmoothCharacterGroupUnramifiedQuadratic_with_category	group
#26092	SubsetsSorted_with_category
#26092	Subsets_sk_with_category
#26064	SymbolicConstantsSubring_with_category
#26162	SymmetricGroup_with_category	group
#26162	TransitiveGroup_with_category	group
#26145	UnivariateProduct_with_category.element_class	product
#26088	UnramifiedExtensionFieldCappedRelative_with_category
#26088	UnramifiedExtensionRingCappedAbsolute_with_category
#26088	UnramifiedExtensionRingCappedRelative_with_category
#26088	UnramifiedExtensionRingFixedMod_with_category
#26058	pAdicAutomorphicForms_with_category
	sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement	Not relevant (appears as an expected result)

New failures in 8.4.beta3:

Ticket	Module	Notes
#26181	Cusps_class
#26177	GRSGaoDecoder
#26177	LinearCodeSyndromeDecoder
#26193	MyModule_with_category
#26198	TestParent4_with_category

Remains in 8.4.b4:

Ticket	Module	Notes
#26221	FreeMonoid_class_with_category
#26218	IntegerVectorsConstraints_with_category
#26261	MPolynomial_polydict
#26091	ProjectiveSpace_rational_field_with_category
#26091	ProjectiveSpace_ring_with_category
#26260	ProductProjectiveSpaces_ring_with_category

Remains in 8.4.b5

|| | |
||-----------------------------------------------|----------------------------|
||Bitset objects are unhashable; use FrozenBitset|Not relevant, but see #24852|
|#26313|AffineSpace_generic_with_category||

Remains in 8.4.b7

| | ||
|------|-----------------------------------------------||
|#26419|LabelledBinaryTrees_with_category.element_class||

CC: @jdemeyer @tscrim @kiwifb @embray @vinklein @zerline

Component: python3

Issue created by migration from https://trac.sagemath.org/ticket/24551

[jdemeyer]

comment:1

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

[embray]

comment:2

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.

[fchapoton]

comment:3

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

I did a few simple cases in #24552

[embray]

comment:4

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]

comment:5

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]

comment:6

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]

comment:7

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]

comment:8

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]

comment:9

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]

comment:10

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]

comment:11

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]

comment:12

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

[fchapoton]

comment:13

see #25586 and #25587 for some partial cure

[fchapoton]

comment:14

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]

comment:15

Note that the changes (taken from comment:2)

diff --git a/src/sage/groups/abelian_gps/abelian_group.py b/src/sage/groups/abelian_gps/abelian_group.py
index e19199b949..bf6fe5dc2c 100644
--- a/src/sage/groups/abelian_gps/abelian_group.py
+++ b/src/sage/groups/abelian_gps/abelian_group.py
@@ -553,6 +553,8 @@ class AbelianGroup_class(UniqueRepresentation, AbelianGroupBase):
             cat = cat.Infinite()
         AbelianGroupBase.__init__(self, category=cat)
 
+    __hash__ = UniqueRepresentation.__hash__
+
     def is_isomorphic(left, right):
         """
         Check whether ``left`` and ``right`` are isomorphic
diff --git a/src/sage/groups/perm_gps/permgroup_named.py b/src/sage/groups/perm_gps/permgroup_named.py
index da1774e96c..54fa034b4a 100644
--- a/src/sage/groups/perm_gps/permgroup_named.py
+++ b/src/sage/groups/perm_gps/permgroup_named.py
@@ -149,6 +149,8 @@ class PermutationGroup_unique(CachedRepresentation, PermutationGroup_generic):
         """
         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]

comment:16

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]

comment:17

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]

comment:18

Confirmed:

diff --git a/src/sage/groups/abelian_gps/abelian_group.py b/src/sage/groups/abelian_gps/abelian_group.py
index e19199b949..62a5e25edb 100644
--- a/src/sage/groups/abelian_gps/abelian_group.py
+++ b/src/sage/groups/abelian_gps/abelian_group.py
@@ -553,6 +553,9 @@ class AbelianGroup_class(UniqueRepresentation, AbelianGroupBase):
             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]

comment:19

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]

comment:20

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

[jhpalmieri]

comment:21

I opened #25940 for ChainComplex_class.

[embray]

comment:22

Added one for HyperellipticCurve_generic in #25946.