Construction from generator may iterate a second time

[yha]

For example, this:

expensive_function(k) = (println(k); k > 2 && error("too large!"))
b = OrderedDict(k => expensive_function(k) for k in 1:3)

prints

1       
2
3
1
2
3
ERROR: too large!

(stack trace omitted)

The constructor shouldn't call my expensive_function again on previous elements.
This seems also to affect some (all?) other structures in DataStructures.jl.

[fingolfin]

So you use a generator expression to compute expensive_function(k) for k equal to 1,2,3. But for k=3 you raise an error. So weird things happen...

But all is fine if I adjust your code to use i > 3:

julia> expensive_function(k) = (println(k); k > 3 && error("too large!"))
expensive_function (generic function with 1 method)

julia> b = OrderedDict(k => expensive_function(k) for k in 1:3)
Base.Generator{UnitRange{Int64}, var"#5#6"}
1
2
3
OrderedDict{Int64, Bool} with 3 entries:
  1 => 0
  2 => 0
  3 => 0

Now the second iteration happens because of this method:

function OrderedDict(kv)
    try
        dict_with_eltype((K, V) -> OrderedDict{K, V}, kv, eltype(kv))
    catch e
        if isempty(methods(iterate, (typeof(kv),))) ||
            !all(x->isa(x, Union{Tuple,Pair}), kv)
            throw(ArgumentError("OrderedDict(kv): kv needs to be an iterator of tuples or pairs"))
        else
            rethrow(e)
        end
    end
end

So if constructing the ordered dict throws an error, it tries to detect if the problem maybe was of a special kind, and if so produces a different error.

Not sure why it does that; Dict definitely doesn't do this. I'll make a PR.

[fingolfin]

Oh I see -- this code changed over time. In Julia 1.6 till 1.10 we still have this the Julia stdlib:

function Dict(kv)
    try
        dict_with_eltype((K, V) -> Dict{K, V}, kv, eltype(kv))
    catch
        if !isiterable(typeof(kv)) || !all(x->isa(x,Union{Tuple,Pair}),kv)
            throw(ArgumentError("Dict(kv): kv needs to be an iterator of tuples or pairs"))
        else
            rethrow()
        end
    end
end

Only 1.11 changed this!

In particular, your issue is triggered in exactly the same way with Julia <= 1.10:

julia> expensive_function(k) = (println(k); k > 2 && error("too large!"))
expensive_function (generic function with 1 method)

julia> b = Dict(k => expensive_function(k) for k in 1:3)
1
2
3
1
2
3
ERROR: too large!
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] expensive_function
   @ ./REPL[1]:1 [inlined]
 [3] #1
   @ ./none:0 [inlined]
 [4] iterate
   @ ./generator.jl:47 [inlined]
 [5] _all
   @ ./reduce.jl:1297 [inlined]
 [6] all
   @ ./reduce.jl:1283 [inlined]
 [7] Dict(kv::Base.Generator{UnitRange{Int64}, var"#1#2"})
   @ Base ./dict.jl:111
 [8] top-level scope
   @ REPL[2]:1

caused by: too large!
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] expensive_function
   @ ./REPL[1]:1 [inlined]
 [3] #1
   @ ./none:0 [inlined]
 [4] iterate
   @ ./generator.jl:47 [inlined]
 [5] Dict{Int64, Bool}(kv::Base.Generator{UnitRange{Int64}, var"#1#2"})
   @ Base ./dict.jl:85
 [6] dict_with_eltype
   @ ./abstractdict.jl:581 [inlined]
 [7] dict_with_eltype
   @ ./abstractdict.jl:588 [inlined]
 [8] Dict(kv::Base.Generator{UnitRange{Int64}, var"#1#2"})
   @ Base ./dict.jl:109
 [9] top-level scope
   @ REPL[2]:1

As such I think there is nothing really here to do, we are just matching Dict's behavior. However I'll adjust my PR to also match it on Julia 1.11.