Opened 22 months ago

Last modified 11 months ago

#24551 closed defect

py3: defining __eq__ breaks inheritance of __hash__ — at Version 39

Reported by: chapoton Owned by:
Priority: major Milestone: sage-8.5
Component: python3 Keywords:
Cc: jdemeyer, tscrim, fbissey, embray, vklein, zerline Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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
#25935AbelianGroupWithValues_class_with_categorygroup
#25935AbelianGroup_class_with_categorygroup
#?????AlternatingGroup_with_categorygroup
#26058BruhatTitsHarmonicCocycles_with_category
#?????CartesianProduct_with_category.element_classproduct
#25940ChainComplex_class_with_category
#?????ClassGroup_with_categorygroup
#?????CompositeConstructionFunctor?functor
#26061CrystalOfAlcovePaths_with_category.element_class
#26087CycleIndexSeriesRing_class_with_category
#?????CyclicPermutationGroup_with_categorygroup
#?????DiCyclicGroup_with_categorygroup
#?????DihedralGroup_with_categorygroup
#26088EisensteinExtensionFieldCappedRelative_with_category
#26088EisensteinExtensionRingCappedAbsolute_with_category
#26088EisensteinExtensionRingCappedRelative_with_category
#26088EisensteinExtensionRingFixedMod_with_category
#?????FiniteWord_list
#?????FiniteWord_str
#?????FiniteWord_tuple
#?????Gamma0_class_with_categorygroup
#?????Gamma1_class_with_categorygroup
#?????GammaH_class_with_categorygroup
#?????Gamma_class_with_categorygroup
#26063HammingCode_with_category
#25946HyperellipticCurve_g2_padic_field_with_category
#25946HyperellipticCurve_g2_rational_field_with_category
#25946HyperellipticCurve_padic_field_with_category
#25946HyperellipticCurve_rational_field_with_category
#?????IdealMonoid_c_with_categoryideal
#?????InfinitePolynomialFunctor?functor
#?????KleinFourGroup_with_categorygroup
#?????LabelledBinaryTrees_with_category.element_class
#?????MPolynomial_polydict
#?????MathieuGroup_with_categorygroup
#26093ModularSymbolsAmbient_wtk_eps_with_category
#?????MultivariateProduct_with_category.element_classproduct
#?????NCPolynomialIdealideal
#?????PGL_with_categorygroup
#?????PSL_with_categorygroup
#?????Partitions_with_constraints_with_category
#?????PolynomialQuotientRing_domain_with_category
#?????PolynomialQuotientRing_field_with_category
#?????PolynomialQuotientRing_generic_with_category
#?????PrimitiveGroup_with_categorygroup
#26091ProjectiveSpace_rational_field_with_category
#26091ProjectiveSpace_ring_with_category
#?????QuaternionFractionalIdeal_rationalideal
#?????QuaternionGroup_with_categorygroup
#?????SL2Z_class_with_categorygroup
#26062ShiftedPrimedTableaux_shape_with_category.element_class
#?????SimplicialSetMorphism?
#26089SmoothCharacterGroupQp_with_categorygroup
#26089SmoothCharacterGroupRamifiedQuadratic_with_categorygroup
#26089SmoothCharacterGroupUnramifiedQuadratic_with_categorygroup
#26092SubsetsSorted_with_category
#26092Subsets_sk_with_category
#26064SymbolicConstantsSubring_with_category
#?????SymmetricGroup_with_categorygroup
#?????TransitiveGroup_with_categorygroup
#?????UnivariateProduct_with_category.element_classproduct
#26088UnramifiedExtensionFieldCappedRelative_with_category
#26088UnramifiedExtensionRingCappedAbsolute_with_category
#26088UnramifiedExtensionRingCappedRelative_with_category
#26088UnramifiedExtensionRingFixedMod_with_category
#26058pAdicAutomorphicForms_with_category
#?????sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement

Change History (39)

comment:1 Changed 22 months ago by jdemeyer

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

comment:2 Changed 22 months ago by embray

  • Component changed from PLEASE CHANGE to python3
  • Type changed from PLEASE CHANGE to defect

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.

comment:3 Changed 22 months ago by chapoton

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

I did a few simple cases in #24552

comment:4 Changed 22 months ago by 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

comment:5 Changed 22 months ago by 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...).

comment:6 Changed 18 months ago by 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).

comment:7 Changed 18 months ago by 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.

comment:8 follow-up: Changed 18 months ago by 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).

comment:9 in reply to: ↑ 8 Changed 18 months ago by 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.

comment:10 Changed 18 months ago by 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.

comment:11 Changed 18 months ago by 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.

comment:12 Changed 18 months ago by 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

comment:13 Changed 17 months ago by chapoton

see #25586 and #25587 for some partial cure

comment:14 Changed 17 months ago by 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'"]

comment:15 Changed 16 months ago by jhpalmieri

Note that the changes (taken from comment:2)

  • src/sage/groups/abelian_gps/abelian_group.py

    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 b class AbelianGroup_class(UniqueRepresentation, AbelianGroupBase): 
    553553            cat = cat.Infinite()
    554554        AbelianGroupBase.__init__(self, category=cat)
    555555
     556    __hash__ = UniqueRepresentation.__hash__
     557
    556558    def is_isomorphic(left, right):
    557559        """
    558560        Check whether ``left`` and ``right`` are isomorphic
  • src/sage/groups/perm_gps/permgroup_named.py

    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 b class PermutationGroup_unique(CachedRepresentation, PermutationGroup_generic): 
    149149        """
    150150        return super(CachedRepresentation, self).__eq__(other)
    151151
     152    __hash__ = CachedRepresentation.__hash__
     153
    152154
    153155class PermutationGroup_symalt(PermutationGroup_unique):
    154156    """

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.

Last edited 16 months ago by jhpalmieri (previous) (diff)

comment:16 Changed 16 months ago by 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.

comment:17 follow-up: Changed 16 months ago by 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.)

comment:18 Changed 16 months ago by jhpalmieri

Confirmed:

  • src/sage/groups/abelian_gps/abelian_group.py

    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 b class AbelianGroup_class(UniqueRepresentation, AbelianGroupBase): 
    553553            cat = cat.Infinite()
    554554        AbelianGroupBase.__init__(self, category=cat)
    555555
     556    def __hash__(self):
     557        return hash(self.elementary_divisors())
     558
    556559    def is_isomorphic(left, right):
    557560        """
    558561        Check whether ``left`` and ``right`` are isomorphic

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

Last edited 16 months ago by jhpalmieri (previous) (diff)

comment:19 in reply to: ↑ 17 Changed 16 months ago by 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__.

comment:20 Changed 16 months ago by jdemeyer

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

comment:21 Changed 16 months ago by jhpalmieri

I opened #25940 for ChainComplex_class.

comment:22 Changed 16 months ago by embray

  • Milestone changed from sage-8.2 to sage-pending

Added one for HyperellipticCurve_generic in #25946.

comment:23 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:24 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:25 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:26 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:27 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:28 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:29 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:30 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:31 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:32 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:33 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:34 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:35 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:36 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:37 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:38 Changed 15 months ago by chapoton

  • Description modified (diff)

comment:39 Changed 15 months ago by chapoton

  • Description modified (diff)
Note: See TracTickets for help on using tickets.