Missing hash methods

[fingolfin]

There are a bunch of our types which implement == but not hash, which leads to confusing behavior and bugs. E.g. for a vector consisting of two such objects which are equal but not identical, the function unique will return a vector with both objects, instead of just one. @YueRen just re-discovered this for Polyhedron, but there are more affected types.

Perhaps someone could write a little script to find more instances semi-automatically (e.g.: iterate over all objects in the Oscar module; for each which is a type, check if there is a custom Base.== method defined; and then for each check if also a custom Base.hash method is defined; if not, print the type).

In the meantime, here is a manual list which is certainly incomplete (and I also might have included some things incorrectly, because I overlooked a hash method). Feel free to edit this list or request changes.

• Cone
• PolyhedralFan (doesn't implement ==)
• Polyhedron
• ToricDivisor (see ToricVarieties: Add Base.hash #1264)
• ...

Also for a few types we should perhaps improve the existing hash methods. E.g. we have this right now:

Base.hash(x::GAPGroup, h::UInt) = h # FIXME
Base.hash(x::GAPGroupElem, h::UInt) = h # FIXME

I think they should at least produce different hashes according to their type. Thus a slightly better approach might be to do something like this:

Base.hash(x::T, h::UInt) where {T <: Union{GAPGroup, GAPGroupElem} = hash(T, h)

But we could still do more, e.g. for permutation groups the degree could be included, and arguably also the order (I mean, computing the order costs us, but if we compute a hash for a group, then we probably will also test equality at some point, and then we need a stabilizer chain anyway, so whatever).

[lgoettgens]

I wrote some small script (NEEDS julia 1.11.1!!!!) to get all cases, including the package that defines the type, and the file and line number the == method is defined (in some nice printing):

list = map(
  filter(names(Oscar; all=true)) do name
    isdefined(Oscar, name) || return false            # remove all wrong exports (see #1964)
    T = getfield(Oscar, name)
    T isa DataType || T isa UnionAll || return false  # remove all non-types and non-parametric-types
    parentmodule(==, (T, T)) == Base && return false  # remove everything without custom ==
    loc = functionloc(==, (T, T))
    endswith(loc[1], "julia/base/Base.jl") && loc[2] == 207 && return false  # remove everything without custom ==
    T <: AbstractArray && endswith(loc[1], "julia/base/abstractarray.jl") && loc[2] == 3028 && return false  # remove AbstractArray subtypes as Base provides both == and hash for them
    parentmodule(hash, (T, UInt)) == Base             # keep iff there is no custom hash
  end,
) do name
  T = getfield(Oscar, name)
  loc = functionloc(==, (T, T))
  if occursin("Oscar.jl/", loc[1])
    loc_cleaned = loc[1][first(findlast("Oscar.jl/", loc[1])):end]
  elseif occursin("packages/", loc[1])
    loc_cleaned = loc[1][(first(findlast("packages/", loc[1])) + length("packages/")):end]
  elseif occursin("julia/base/", loc[1])
    loc_cleaned = loc[1][first(findlast("julia/base/", loc[1])):end]
  else
    loc_cleaned = loc[1]
  end
  name, parentmodule(T), (loc_cleaned, loc[2])
end;

Currently (on cd79a0b), I get the following list of things:

julia> show(IOContext(stdout, :limit => false), "text/plain", list)
6-element Vector{Tuple{Symbol, Module, Tuple{String, Int32}}}:
 (:ClassField, Hecke, ("Hecke/3LoSB/src/RCF/class_fields.jl", 240))
 (:FinGenAbGroupHom, Hecke, ("Hecke/3LoSB/src/GrpAb/Map.jl", 217))
 (:FractionalIdeal, Oscar, ("Oscar.jl/src/Rings/FractionalIdeal.jl", 55))
 (:GenOrdFracIdl, Hecke, ("Hecke/3LoSB/src/GenOrd/FractionalIdeal.jl", 272))
 (:OrdLocElem, Hecke, ("AbstractAlgebra/lVsyJ/src/NCRings.jl", 86))
 (:SLPoly, Oscar, ("AbstractAlgebra/lVsyJ/src/NCRings.jl", 86))

One needs unfortunately to check the == methods by hand. If they are just delegating to objectid(-) == objected(-), I would propose to remove them, to make disappear from this list.

[lgoettgens]

Currently (on cd79a0b), I get the following list of things:

julia> show(IOContext(stdout, :limit => false), "text/plain", list)
6-element Vector{Tuple{Symbol, Module, Tuple{String, Int32}}}:
 (:ClassField, Hecke, ("Hecke/3LoSB/src/RCF/class_fields.jl", 240))
 (:FinGenAbGroupHom, Hecke, ("Hecke/3LoSB/src/GrpAb/Map.jl", 217))
 (:FractionalIdeal, Oscar, ("Oscar.jl/src/Rings/FractionalIdeal.jl", 55))
 (:GenOrdFracIdl, Hecke, ("Hecke/3LoSB/src/GenOrd/FractionalIdeal.jl", 272))
 (:OrdLocElem, Hecke, ("AbstractAlgebra/lVsyJ/src/NCRings.jl", 86))
 (:SLPoly, Oscar, ("AbstractAlgebra/lVsyJ/src/NCRings.jl", 86))

After new releases of Hecke and AA are now available here, the list is now drastically shorter.

[lgoettgens]

@thofma will have a look at the remaining few Hecke ones.

FractionalIdeal will just need a dummy hash function. (see #4428)

SLPoly can get some proper hash function, but this will need a few more hash functions for all types that occur inside of it.

[thofma]

thofma/Hecke.jl#1719

[lgoettgens]

I have an updated script for finding more offending cases. The previous iteration missed all non-exported types in submodules (e.g. Oscar.StraightLinePrograms.SLProgram), and all equality functions with type parameters (i.e. ==(ParametricType{T}, ParametricType{T}) where T). The following script should find all of these as well, in all of Oscar, Hecke, Nemo, AA, and their submodules.

script:

typelist = [];

for package in [Oscar, Hecke, Nemo, AbstractAlgebra]
  Oscar.walkmodules(package) do mod
    append!(typelist, filter(!isnothing, map(methods(==, mod)) do meth
      meth.nargs == 3 || return nothing
      sig = Base.unwrap_unionall(meth.sig)
      arg1_type = sig.types[2]
      arg2_type = sig.types[3]
      arg1_type == arg2_type || return nothing                  # arg1 and arg2 must have the same type to be considered atm
      T = arg1_type
      meth.module == Base && return nothing                     # remove everything without custom ==
      parentmodule(hash, (T, UInt)) == Base || return nothing   # remove everything with custom hash
      T
    end))
  end;
end;

list = map(typelist) do T
  loc = functionloc(==, (T, T))
  if occursin("Oscar.jl/", loc[1])
    loc_cleaned = loc[1][first(findlast("Oscar.jl/", loc[1])):end]
  elseif occursin("packages/", loc[1])
    loc_cleaned = loc[1][(first(findlast("packages/", loc[1])) + length("packages/")):end]
  elseif occursin("julia/base/", loc[1])
    loc_cleaned = loc[1][first(findlast("julia/base/", loc[1])):end]
  else
    loc_cleaned = loc[1]
  end
  T, (T isa TypeVar ? parentmodule(T.ub) : parentmodule(T)), (loc_cleaned, loc[2])
end;

show(IOContext(stdout, :limit => false), "text/plain", list)

current list (as of 91f076a):

julia> show(IOContext(stdout, :limit => false), "text/plain", list)
68-element Vector{Tuple{Any, Module, Tuple{String, Int32}}}:
 (Oscar.FractionalIdeal, Oscar, ("Oscar.jl/src/Rings/FractionalIdeal.jl", 55))
 (Oscar.OrderedMultiIndex{T}, Oscar, ("Oscar.jl/src/Combinatorics/OrderedMultiIndex.jl", 93))
 (SLPoly{T, SLPR} where SLPR<:(SLPolyRing{T}), Oscar, ("Oscar.jl/src/Rings/slpolys.jl", 331))
 (SubquoModule{T<:AbsLocalizedRingElem}, Oscar, ("Oscar.jl/src/Modules/missing_functionality.jl", 76))
 (SubquoModule{T}, Oscar, ("Oscar.jl/src/Modules/UngradedModules/SubquoModule.jl", 1051))
 (Oscar.PartialCharacter{T<:FieldElem}, Oscar, ("Oscar.jl/src/Rings/binomial_ideals.jl", 408))
 (Oscar.GaloisGrp.BoundRingElem, Oscar.GaloisGrp, ("Oscar.jl/src/NumberTheory/GaloisGrp/GaloisGrp.jl", 69))
 (Oscar.GrpCoh.CoChain{N, G, M}, Oscar.GrpCoh, ("Oscar.jl/experimental/GModule/src/Cohomology.jl", 642))
 (Oscar.GrpExt_module.GrpExtElem, Oscar.GrpExt_module, ("Oscar.jl/experimental/GModule/src/GrpExt.jl", 78))
 (Oscar.StraightLinePrograms.Minus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 265))
 (Oscar.StraightLinePrograms.UniMinus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 285))
 (Oscar.StraightLinePrograms.Lazy, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 48))
 (Oscar.StraightLinePrograms.Decision, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 366))
 (Oscar.StraightLinePrograms.Getindex, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 451))
 (Oscar.StraightLinePrograms.List, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 400))
 (Oscar.StraightLinePrograms.Exp, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 332))
 (Oscar.StraightLinePrograms.Plus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 244))
 (Oscar.StraightLinePrograms.Call, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 477))
 (Oscar.StraightLinePrograms.Times, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 311))
 (Oscar.StraightLinePrograms.Gen, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 217))
 (Oscar.StraightLinePrograms.Compose, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 426))
 (Oscar.StraightLinePrograms.Input, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 195))
 (Oscar.StraightLinePrograms.SLProgram, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/straightline.jl", 146))
 (Oscar.StraightLinePrograms.Const, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 173))
 (Oscar.StraightLinePrograms.LazyRec, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 137))
 (Oscar.StraightLinePrograms.Minus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 265))
 (Oscar.StraightLinePrograms.UniMinus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 285))
 (Oscar.StraightLinePrograms.Lazy, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 48))
 (Oscar.StraightLinePrograms.Decision, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 366))
 (Oscar.StraightLinePrograms.Getindex, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 451))
 (Oscar.StraightLinePrograms.List, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 400))
 (Oscar.StraightLinePrograms.Exp, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 332))
 (Oscar.StraightLinePrograms.Plus, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 244))
 (Oscar.StraightLinePrograms.Call, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 477))
 (Oscar.StraightLinePrograms.Times, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 311))
 (Oscar.StraightLinePrograms.Gen, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 217))
 (Oscar.StraightLinePrograms.Compose, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 426))
 (Oscar.StraightLinePrograms.Input, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 195))
 (Oscar.StraightLinePrograms.SLProgram, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/straightline.jl", 146))
 (Oscar.StraightLinePrograms.Const, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 173))
 (Oscar.StraightLinePrograms.LazyRec, Oscar.StraightLinePrograms, ("Oscar.jl/src/StraightLinePrograms/lazy.jl", 137))
 (Oscar.SubfieldLattice_Module.SubfieldLatticeElem, Oscar.SubfieldLattice_Module, ("Oscar.jl/experimental/GaloisGrp/src/Subfields.jl", 98))
 (Hecke.MapParent, Hecke, ("Hecke/ULkko/src/GrpAb/Map.jl", 506))
 (Hecke.CMType, Hecke, ("Hecke/ULkko/src/NumField/CM.jl", 60))
 (FinGenAbGroupHom, Hecke, ("Hecke/ULkko/src/GrpAb/Map.jl", 217))
 (OrdLocElem{T<:AbsSimpleNumFieldElem}, Hecke, ("Hecke/ULkko/src/Misc/OrdLocalization.jl", 206))
 (Hecke.AbsAlgAssIdl, Hecke, ("Hecke/ULkko/src/AlgAss/Ideal.jl", 294))
 (Hecke.RelNumFieldOrder, Hecke, ("Hecke/ULkko/src/NumFieldOrd/NfRelOrd/NfRelOrd.jl", 616))
 (ClassField, Hecke, ("Hecke/ULkko/src/RCF/class_fields.jl", 240))
 (Hecke.ModAlgAssElem{P, T}, Hecke, ("Hecke/ULkko/src/ModAlgAss/ModAlgAss.jl", 120))
 (Hecke.RCFCharacter, Hecke, ("Hecke/ULkko/src/RCF/rcf_stark.jl", 23))
 (Hecke.QuadSpaceCls, Hecke, ("Hecke/ULkko/src/QuadForm/Quad/Spaces.jl", 2340))
 (Hecke.AbsNumFieldOrderIdealSet, Hecke, ("Hecke/ULkko/src/NumFieldOrd/NfOrd/Ideal/Ideal.jl", 69))
 (Hecke.RelFinFieldElem{S, T}, Hecke, ("Hecke/ULkko/src/Misc/RelFiniteField.jl", 144))
 (T<:Hecke.ModAlgAssLat, Hecke, ("Hecke/ULkko/src/ModAlgAss/Lattices/Basics.jl", 192))
 (GenOrdFracIdl, Hecke, ("Hecke/ULkko/src/GenOrd/FractionalIdeal.jl", 272))
 (Hecke.AlgAssAbsOrd, Hecke, ("Hecke/ULkko/src/AlgAssAbsOrd/Order.jl", 543))
 (HypellCrv{T}, Hecke, ("Hecke/ULkko/src/HypellCrv/HypellCrv.jl", 218))
 (Hecke.AlgAssAbsOrdIdlSet, Hecke, ("Hecke/ULkko/src/AlgAssAbsOrd/Ideal.jl", 1492))
 (Hecke.AlgAssRelOrdIdl{S, T, U}, Hecke, ("Hecke/ULkko/src/AlgAssRelOrd/Ideal.jl", 729))
 (HypellCrvPt{T}, Hecke, ("Hecke/ULkko/src/HypellCrv/HypellCrv.jl", 490))
 (Hecke.AlgAssRelOrd, Hecke, ("Hecke/ULkko/src/AlgAssRelOrd/Order.jl", 371))
 (Hecke.LocalQuadSpaceCls, Hecke, ("Hecke/ULkko/src/QuadForm/Quad/Spaces.jl", 2144))
 (Hecke.AbsNumFieldOrderFractionalIdealSet, Hecke, ("Hecke/ULkko/src/NumFieldOrd/NfOrd/FracIdeal.jl", 169))
 (Hecke.IE.FactoredIdeal, Hecke.IE, ("Hecke/ULkko/src/NumFieldOrd/NfOrd/Ideal/Enum.jl", 20))
 (AbstractAlgebra.FPModule{T<:RingElement}, AbstractAlgebra, ("AbstractAlgebra/xy6Re/src/Module.jl", 198))
 (AbstractAlgebra.Generic.SymmetricGroup, AbstractAlgebra.Generic, ("AbstractAlgebra/xy6Re/src/generic/PermGroups.jl", 406))
 (AbstractAlgebra.Generic.QuotientModule{T<:RingElement}, AbstractAlgebra.Generic, ("AbstractAlgebra/xy6Re/src/generic/QuotientModule.jl", 101))