Unexpected behavior of get!(f::Function, collection, key)

[bkamins]

Function get!(f::Function, collection, key) makes the following steps in case key is not found in the dictionary:

1. gets index: index = ht_keyindex2(h, key)
2. evaluates default: v = convert(V, default())
3. sets new key,value pair: _setindex!(h, v, key, -index)

This sequence might produce wrong results if default() changes the underlying dictionary.

Possible solutions:

1. make it clear in the documentation that default may not change the dictionary;
2. change _setindex!(h, v, key, -index) to h[k] = v (this would reduce the performance of get! because we have to calculate index twice);
3. add a keyword parameter to get! definition get!{K,V}(default::Callable, h::Dict{K,V}, key0; stable::Bool=false), where stable indicates that default does not change the dictionary (and is false by default) and using this parameter execute appropriate code.

[stevengj]

I vote for 1. I don't see a compelling reason to support a default that changes the dictionary.

[bkamins]

It can occur when you use memoization. Consider the following basic example:

cache1 = Dict{Int, BigInt}()
cache2 = Dict{Int, BigInt}()

function fib1(n::Int)
    @assert n >= 0
    get!(cache1, n) do
        return n == 0 ? BigInt(1) : BigInt(n) * fib1(n - 1)
    end
end

function fib2(n::Int)
    @assert n >= 0
    if n in cache2
        return cache2[n]
    end
    v = n == 0 ? BigInt(1) : BigInt(n) * fib2(n - 1)
    cache2[n] = v
    return v
end

println(fib1(50))
println(length(cache1)) # should be 51
println(fib2(50))
println(length(cache2)) # is 51

which produces

30414093201713378043612608166064768844377641568960512000000000000
26
30414093201713378043612608166064768844377641568960512000000000000
51

And we wee that using get! does not work correctly.

[JeffBezanson]

Indeed, if we didn't intend option (1), this function would not even exist. The only purpose of it is performance.

Another option is to add an internal dirty flag to Dict that we can use to detect modification.

[simonster]

Dup of #7944