`keys(g::Generator) = keys(g.iter)` is not generically correct and should not be defined

[adienes]

from the keys docstring:

keys(iterator)
For an iterator or collection that has keys and values (e.g. arrays and dictionaries), return an iterator over the keys.

but a Generator does not have keys and values. it only has values. there is no get(::Generator, ...) nor getindex(::Generator, ...)

I believe a similar problem holds for axes(g::Generator) and ndims(g::Generator), but I'm focusing on keys since it seems the most flagrant.

this leads to awful behavior with things like

julia> d
Dict{Symbol, Int64} with 2 entries:
  :a => 1
  :b => -1

julia> findmax(identity, d)
(1, :a)

julia> findmax(Iterators.map(identity, d))
(:b => -1, :b)

where the second call should either error, or maybe a Generator could 1-index as if it were an enumerate so that would become

julia> findmax(Iterators.map(identity, d))
(:b => -1, 2)

note that

julia> iterate(Iterators.map(identity, d))
(:a => 1, 2)

so even the state in iterate is 1-indexed and not taking from keys(g.iter)

I think technically this is a duplicate of #48379, but I don't think the fundamental problem there has anything to do with skipmissing so I just made a new issue.

[nsajko]

The method was added here, and approved by triage multiple times it seems: #34678

[adienes]

how unfortunate. well, it's not documented behavior so it's not too late to revert. note that the triage approval summary contained the language doesn't seem harmful.

but it is harmful, as it makes some basic functions in Base violate their docstring.

[jariji]

Since Generator doesn't implement getindex I don't see a need for it to implement keys. As Takafumi said in the original PR, we should expect

isequal(collect(values(A)), [A[k] for k in keys(A)])

and Generator isn't intended to support random access like that.

So I'd favor an error over the enumerate- or countfrom-style behavior.

[jariji]

I think it would be good to get this done because it's a correctness hazard. Is this ready for triage?

[adienes]

as @nsajko noted, this behavior was already considered and approved by triage in #34678. I don't have a productive solution that wouldn't be very breaking, so I'm not sure what there is for triage to discuss. I should probably just close this as won't fix

although, I will also note that the findmax(itr) docstring doesn't make much sense

Indices are of the same type as those returned by keys(itr) and pairs(itr).

... so which is it? keys or pairs ? those are different sometimes

[mbauman]

I'm still trying to figure out what exactly makes this wrong. Because it's definitely right in other cases. Most notably, we need generators to expose their iteration space's axes in order to collect them to the right shape. That is:

julia> g = (i*j for i in 1:3, j in 1:4)
Base.Generator{Base.Iterators.ProductIterator{Tuple{UnitRange{Int64}, UnitRange{Int64}}}, var"#5#6"}(var"#5#6"(), Base.Iterators.ProductIterator{Tuple{UnitRange{Int64}, UnitRange{Int64}}}((1:3, 1:4)))

julia> Base.IteratorSize(g)
Base.HasShape{2}()

julia> axes(g)
(Base.OneTo(3), Base.OneTo(4))

That's not only correct, but it's precisely what's needed in order to collect(g) (that is: comprehensions!) into the correct shape. Now yes, I know that's not keys (and in fact keys(g) in this case errors because the ProductIterator is a non-indexable iterable). But it's a starting point for me talking out loud here.

I think this is the same fundamental problem as map (#57075) — generators support both iterables and indexables, and the mismatch happens when there are datastructures for whom indexing and iteration disagree. That's what's happening with findmax:

julia> d = Dict(:a=>1, :b=>-1);

julia> findmax(d) # indexing-based
(1, :a)

julia> findmax(kv for kv in d) # iteration based
(:b => -1, :b)

julia> findmax(v for (k,v) in d) # FTFY!
(1, :a)

Is the second one there actually wrong? The key-value pair (:b => -1) is indeed "greater" than (:a => -1)... and yeah, it occurs at the "key" :b. Yes, it's surprising and yes, it's a footgun, but why is it wrong?

[adienes]

I actually mostly agree with you that this is p r o b a b l y closer to "footgun caused by the intersection of vague interfaces" than it is to "correctness bug"

but consider

julia> d = Dict([:a => 1, :b => -1]);

julia> it = Iterators.map(identity, d);

julia> pairs(it)
Base.Generator{Base.Iterators.Zip{Tuple{Base.KeySet{Symbol, Dict{Symbol, Int64}}, Base.Generator{Dict{Symbol, Int64}, typeof(identity)}}}, Base.var"#Generator##2#Generator##3"{Pair}}(Base.var"#Generator##2#Generator##3"{Pair}(), zip([:a, :b], Base.Generator{Dict{Symbol, Int64}, typeof(identity)}(identity, Dict(:a => 1, :b => -1))))

why is this allowed? namely: that keys forwards to the dictionary but values does not, and we just get a Generator{Dict...}

pairs demands that

keys(a), values(a) and pairs(a) all iterate a and return the elements in the same order.

but this is not guaranteed generically here! imagine I make a dictionary type FunDict where

iterate(::FunDict) = # iterates in whatever order the hash key rng decides
keys(::FunDict) = # sort the keys alphabetically
values(::FunDict) = # sort the keys alphabetically, get each associated value

then pairs(Iterators.map(identity, ::FunDict)) will be a Zip of keys and values that are completely misaligned

(never mind the fact that pairs says it returns an iterator over key => value pairs for any collection that maps a set of keys to a set of values, and a Generator is not such a collection)

[mbauman]

why is this allowed? namely: that keys forwards to the dictionary but values does not, and we just get a Generator{Dict...}

But isn't this all just doing the right thing? The generator is exposing the iteration space of a collection over a set of its keys — we can literally write for kv in d! The values of the generator will be the result of iterating the collection. Which, yeah, is exactly the collection itself!

pairs demands that

keys(a), values(a) and pairs(a) all iterate a and return the elements in the same order.

You lost the styling from the docstring there, but perhaps that's even better because it makes it clear where the ambiguity lies. Is it the English "iterate" or the Julia function iterate? I think it needs to be the latter — iterate itself is a part of that ordering requirement!

Make a data structure that breaks that requirement, and generators will happily forward along that brokenness.

---

Perhaps the hardest part here is knowing when some f in findmax(f(d)) is using iterate over the keys vs. when it's generating values over the keys vs. when it's discarding the original keys in favor of a new set. Digging into the Iterators module is a good signal, but I can see how skipmissing would be quite ambiguous.

[adienes]

I'd like to repeat my previous example with some code --- not because I don't think you understood it, but just so I can see very specifically where our disagreement begins.

using Random

struct FunDict{K, V}
    d::Dict{K, V}
end

import Base: keys, values, length, iterate
keys(fd::FunDict) = sort(keys(fd.d))
values(fd::FunDict) = [fd.d[k] for k in keys(fd)]

length(fd::FunDict) = length(fd.d)
iterate(fd::FunDict) = iterate(fd.d)
iterate(fd::FunDict, i) = iterate(fd.d, i)

Random.seed!(1)
d = Dict(zip(randstring.(5 .* ones(Int, 5)), rand(5)))
fd = FunDict(d)
it = Iterators.map(identity, fd)

this produces

julia> collect(pairs(it))
5-element Vector{Pair{String, Pair{String, Float64}}}:
 "4Lhcu" => ("XcGqU" => 0.7305508461555176)
 "BlmfA" => ("4Lhcu" => 0.9003405842788204)
 "XcGqU" => ("ZSI0Z" => 0.8686942572391998)
 "ZSI0Z" => ("BlmfA" => 0.37215957409032674)
 "cC0J7" => ("cC0J7" => 0.8667711192602672)

I am currently inferring from your response that you would describe this as a broken data structure, and not meeting the contract of one or both of pairs and iterate, is that correct? if so it's an interesting distinction as I had been reading the docstring to mean something more like enforcing pairs(x) == zip(keys(x), values(x)) without requiring anything of iterate

also note of course that it is not the case that values(x) yields the same elements as iterating over x

[jariji]

I might be way behind here, but I'd like to try articulating my own view.

Imho the gospel should be that keys returns indices that are valid under getindex.

Generator could define getindex as either Iterators.nth, or as g.iter[i]

To demonstrate, take the case of

julia> g = (x for x in Dict(:a => 10))
Base.Generator{Dict{Symbol, Int64}, typeof(identity)}(identity, Dict(:a => 10))

If g[i] is nth(g, i), then keys(g) needs to be [1] because 1 is the only value for which nth(g, i) returns a value. That's not currently what it does.

julia> keys(g)
KeySet for a Dict{Symbol, Int64} with 1 entry. Keys:
  :a

If g[i] is g.iter[i], then keys(g) needs to return keys(g.iter), whose elements are [:a]. Then consulting findmax we have

findmax(f, domain) -> (f(x), index)

Return a pair of a value in the codomain (outputs of f) and the index or key of the corresponding value in the domain (inputs to f) such that f(x) is maximised. If there are multiple maximal points, then the first one will be returned.

domain must be a non-empty iterable supporting keys. Indices are of the same type as those returned by keys(domain).

and

julia> findmax(identity, g)
(:a => 10, :a)

where :a is the key i where g[i] attains its maximum, which is right, and :a => 10 is purported to be the value g[i] at that i, but that is wrong: the value of g[i] is 10, not :a => 10.

I think therefore that defining keys(::Generator) necessitates violating my gospel assumption that keys(g) returns indices i for which getindex(g, i) returns values. Do we think that's right? Are we ok with it?