Revision ed7b069f9c857ab0eec7972350b21d9e92d696cc authored by Logan Kilpatrick on 15 April 2021, 20:12:19 UTC, committed by GitHub on 15 April 2021, 20:12:19 UTC
Co-authored-by: Max Horn <max@quendi.de>
1 parent 691cf74
hashing.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
using Random, LinearAlgebra, SparseArrays
isdefined(Main, :OffsetArrays) || @eval Main include("testhelpers/OffsetArrays.jl")
using .Main.OffsetArrays
types = Any[
Bool,
Int8, UInt8, Int16, UInt16, Int32, UInt32, Int64, UInt64, Float32, Float64,
Rational{Int8}, Rational{UInt8}, Rational{Int16}, Rational{UInt16},
Rational{Int32}, Rational{UInt32}, Rational{Int64}, Rational{UInt64}
]
vals = vcat(
typemin(Int64),
-Int64(maxintfloat(Float64)) .+ Int64[-4:1;],
typemin(Int32),
-Integer(maxintfloat(Float32)) .+ (-4:1),
-2:2,
Integer(maxintfloat(Float32)) .+ (-1:4),
typemax(Int32),
Int64(maxintfloat(Float64)) .+ Int64[-1:4;],
typemax(Int64),
)
function coerce(T::Type, x)
if T<:Rational
convert(T, coerce(typeof(numerator(zero(T))), x))
elseif !(T<:Integer)
convert(T, x)
else
x % T
end
end
for T = types[2:end], x = vals
a = coerce(T, x)
@test hash(a, zero(UInt)) == invoke(hash, Tuple{Real, UInt}, a, zero(UInt))
@test hash(a, one(UInt)) == invoke(hash, Tuple{Real, UInt}, a, one(UInt))
end
let collides = 0
for T = types, S = types, x = vals
a = coerce(T, x)
b = coerce(S, x)
eq = hash(a) == hash(b)
#println("$(typeof(a)) $a")
#println("$(typeof(b)) $b")
if isequal(a, b)
@test eq
else
collides += eq
end
end
# each pair of types has one collision for these values
@test collides <= (length(types) - 1)^2
end
@test hash(0.0) != hash(-0.0)
# issue #8619
@test hash(nextfloat(2.0^63)) == hash(UInt64(nextfloat(2.0^63)))
@test hash(prevfloat(2.0^64)) == hash(UInt64(prevfloat(2.0^64)))
# issue #9264
@test hash(1//6,zero(UInt)) == invoke(hash, Tuple{Real, UInt}, 1//6, zero(UInt))
@test hash(1//6) == hash(big(1)//big(6))
@test hash(1//6) == hash(0x01//0x06)
# hashing collections (e.g. issue #6870)
vals = Any[
[1,2,3,4], [1 3;2 4], Any[1,2,3,4], [1,3,2,4],
[1.0, 2.0, 3.0, 4.0], BigInt[1, 2, 3, 4],
[1,0], [true,false], BitArray([true,false]),
# Irrationals
Any[1, pi], [1, pi], [pi, pi], Any[pi, pi],
# Overflow with Int8
Any[Int8(127), Int8(-128), -383], 127:-255:-383,
# Loss of precision with Float64
Any[-Int64(2)^53-1, 0.0, Int64(2)^53+1], [-Int64(2)^53-1, 0, Int64(2)^53+1],
(-Int64(2)^53-1):Int64(2)^53+1:(Int64(2)^53+1),
# Some combinations of elements support -, others do not
[1, 2, "a"], [1, "a", 2], [1, 2, "a", 2], [1, 'a', 2],
Set([1,2,3,4]),
Set([1:10;]), # these lead to different key orders
Set([7,9,4,10,2,3,5,8,6,1]), #
Dict(42 => 101, 77 => 93), Dict{Any,Any}(42 => 101, 77 => 93),
(1,2,3,4), (1.0,2.0,3.0,4.0), (1,3,2,4),
("a","b"), (SubString("a",1,1), SubString("b",1,1)),
# issue #6900
Dict(x => x for x in 1:10),
Dict(7=>7,9=>9,4=>4,10=>10,2=>2,3=>3,8=>8,5=>5,6=>6,1=>1),
[], [1], [2], [1, 1], [1, 2], [1, 3], [2, 2], [1, 2, 2], [1, 3, 3],
zeros(2, 2), spzeros(2, 2), Matrix(1.0I, 2, 2), sparse(1.0I, 2, 2),
sparse(fill(1., 2, 2)), fill(1., 2, 2), sparse([0 0; 1 0]), [0 0; 1 0],
[-0. 0; -0. 0.], SparseMatrixCSC(2, 2, [1, 3, 3], [1, 2], [-0., -0.]),
# issue #16364
1:4, 1:1:4, 1:-1:0, 1.0:4.0, 1.0:1.0:4.0, range(1, stop=4, length=4),
# issue #35597, when `LinearIndices` does not begin at 1
Base.IdentityUnitRange(2:4),
OffsetArray(1:4, -2),
OffsetArray([1 3; 2 4], -2, 2),
OffsetArray(1:4, 0),
OffsetArray([1 3; 2 4], 0, 0),
'a':'e', ['a', 'b', 'c', 'd', 'e'],
# check that hash is still consistent with heterogeneous arrays for which - is defined
# for some pairs and not others
["a", "b", 1, 2], ["a", 1, 2], ["a", "b", 2, 2], ["a", "a", 1, 2], ["a", "b", 2, 3]
]
for a in vals, b in vals
@test isequal(a,b) == (hash(a)==hash(b))
end
for a in vals
a isa AbstractArray || continue
aa = copyto!(Array{eltype(a)}(undef, size(a)), a)
aaa = copyto!(Array{Any}(undef, size(a)), a)
if keys(a) == keys(aa)
@test hash(a) == hash(aa) == hash(aaa)
else
@test hash(a) == hash(OffsetArray(aa, (first.(axes(a)).-1)...)) == hash(OffsetArray(aaa, (first.(axes(a)).-1)...))
end
end
vals = Any[
Int[], Float64[],
[0], [1], [2],
# test vectors starting with ranges
[1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6],
[2, 1], [3, 2, 1], [4, 3, 2, 1], [5, 4, 3, 2, 1], [5, 4, 3, 2, 1, 0, -1],
# test vectors starting with ranges which trigger overflow with Int8
[124, 125, 126, 127], [124, 125, 126, 127, -128], [-128, 127, -128],
# test vectors including ranges
[2, 1, 2, 3], [2, 3, 2, 1], [2, 1, 2, 3, 2], [2, 3, 2, 1, 2],
# test various sparsity patterns
[0, 0], [0, 0, 0], [0, 1], [1, 0],
[0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 1, 2],
[0 0; 0 0], [1 0; 0 0], [0 1; 0 0], [0 0; 1 0], [0 0; 0 1],
[5 1; 0 0], [1 1; 0 1], [0 2; 3 0], [0 2; 4 6], [4 0; 0 1],
[0 0 0; 0 0 0], [1 0 0; 0 0 1], [0 0 2; 3 0 0], [0 0 7; 6 1 2],
[4 0 0; 3 0 1], [0 2 4; 6 0 0],
# various stored zeros patterns
sparse([1], [1], [0]), sparse([1], [1], [-0.0]),
sparse([1, 2], [1, 1], [-0.0, 0.0]), sparse([1, 2], [1, 1], [0.0, -0.0]),
sparse([1, 2], [1, 1], [-0.0, 0.0], 3, 1), sparse([1, 2], [1, 1], [0.0, -0.0], 3, 1),
sparse([1, 3], [1, 1], [-0.0, 0.0], 3, 1), sparse([1, 3], [1, 1], [0.0, -0.0], 3, 1),
sparse([1, 2, 3], [1, 1, 1], [-1, 0, 1], 3, 1), sparse([1, 2, 3], [1, 1, 1], [-1.0, -0.0, 1.0], 3, 1),
sparse([1, 3], [1, 1], [-1, 0], 3, 1), sparse([1, 2], [1, 1], [-1, 0], 3, 1)
]
for a in vals
b = Array(a)
@test hash(convert(Array{Any}, a)) == hash(b)
@test hash(convert(Array{supertype(eltype(a))}, a)) == hash(b)
@test hash(convert(Array{Float64}, a)) == hash(b)
@test hash(sparse(a)) == hash(b)
if !any(x -> isequal(x, -0.0), a)
@test hash(convert(Array{Int}, a)) == hash(b)
if all(x -> typemin(Int8) <= x <= typemax(Int8), a)
@test hash(convert(Array{Int8}, a)) == hash(b)
end
end
end
# Test that overflow does not give inconsistent hashes with heterogeneous arrays
@test hash(Any[Int8(1), Int8(2), 255]) == hash([1, 2, 255])
@test hash(Any[Int8(127), Int8(-128), 129, 130]) ==
hash([127, -128, 129, 130]) != hash([127, 128, 129, 130])
# Test hashing sparse matrix with type which does not support -
struct CustomHashReal
x::Float64
end
Base.hash(x::CustomHashReal, h::UInt) = hash(x.x, h)
Base.:(==)(x::CustomHashReal, y::Number) = x.x == y
Base.:(==)(x::Number, y::CustomHashReal) = x == y.x
Base.zero(::Type{CustomHashReal}) = CustomHashReal(0.0)
Base.zero(x::CustomHashReal) = zero(CustomHashReal)
let a = sparse([CustomHashReal(0), CustomHashReal(3), CustomHashReal(3)])
@test hash(a) == hash(Array(a))
end
vals = Any[
0.0:0.1:0.3, 0.3:-0.1:0.0,
0:-1:1, 0.0:-1.0:1.0, 0.0:1.1:10.0, -4:10,
'a':'e', 'b':'a',
range(1, stop=1, length=1), range(0.3, stop=1.0, length=3), range(1, stop=1.1, length=20)
]
for a in vals
@test hash(Array(a)) == hash(a)
end
@test hash(SubString("--hello--",3,7)) == hash("hello")
@test hash(:(X.x)) == hash(:(X.x))
@test hash(:(X.x)) != hash(:(X.y))
@test hash([1,2]) == hash(view([1,2,3,4],1:2))
let a = QuoteNode(1), b = QuoteNode(1.0)
@test (hash(a)==hash(b)) == (a==b)
end
let a = Expr(:block, Core.TypedSlot(1, Any)),
b = Expr(:block, Core.TypedSlot(1, Any)),
c = Expr(:block, Core.TypedSlot(3, Any))
@test a == b && hash(a) == hash(b)
@test a != c && hash(a) != hash(c)
@test b != c && hash(b) != hash(c)
end
@test hash(Dict(),hash(Set())) != hash(Set(),hash(Dict()))
# issue 15659
for prec in [3, 11, 15, 16, 31, 32, 33, 63, 64, 65, 254, 255, 256, 257, 258, 1023, 1024, 1025],
v in Any[-0.0, 0, 1, -1, 1//10, 2//10, 3//10, 1//2, pi]
setprecision(prec) do
x = convert(BigFloat, v)
@test precision(x) == prec
num, pow, den = Base.decompose(x)
y = num*big(2.0)^pow/den
@test precision(y) == prec
@test isequal(x, y)
end
end
# issue #20744
@test hash(:c, hash(:b, hash(:a))) != hash(:a, hash(:b, hash(:c)))
# issue #5849, objectid of types
@test Vector === (Array{T,1} where T)
@test (Pair{A,B} where A where B) !== (Pair{A,B} where B where A)
let vals_expr = :(Any[Vector, (Array{T,1} where T), 1, 2, Union{Int, String}, Union{String, Int},
(Union{String, T} where T), Ref{Ref{T} where T}, (Ref{Ref{T}} where T),
(Vector{T} where T<:Real), (Vector{T} where T<:Integer),
(Vector{T} where T>:Integer),
(Pair{A,B} where A where B), (Pair{A,B} where B where A)])
vals_a = eval(vals_expr)
vals_b = eval(vals_expr)
for (i, a) in enumerate(vals_a), (j, b) in enumerate(vals_b)
@test i != j || (a === b)
@test (a === b) == (objectid(a) == objectid(b))
end
end
# issue #26038
let p1 = Ptr{Int8}(1), p2 = Ptr{Int32}(1), p3 = Ptr{Int8}(2)
@test p1 == p2
@test !isequal(p1, p2)
@test p1 != p3
@test hash(p1) != hash(p2)
@test hash(p1) != hash(p3)
@test hash(p1) == hash(Ptr{Int8}(1))
@test p1 < p3
@test !(p1 < p2)
@test isless(p1, p3)
@test_throws MethodError isless(p1, p2)
end
# PR #40083
@test hash(1:1000) == hash(collect(1:1000))
@testset "test the other core data hashing functions" begin
@testset "hash_64_32" begin
vals = vcat(
typemin(UInt64) .+ UInt64[1:4;],
typemax(UInt64) .- UInt64[4:-1:0;]
)
for a in vals, b in vals
@test isequal(a, b) == (Base.hash_64_32(a) == Base.hash_64_32(b))
end
end
@testset "hash_32_32" begin
vals = vcat(
typemin(UInt32) .+ UInt32[1:4;],
typemax(UInt32) .- UInt32[4:-1:0;]
)
for a in vals, b in vals
@test isequal(a, b) == (Base.hash_32_32(a) == Base.hash_32_32(b))
end
end
end
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...