# Iterator bug?

I just tested @Dan’s (?) answer on SO ( Julia - the way of kings (generator performance) - Stack Overflow )

There is function allSAWs(neigh, pathlen) which return iterator. His algorithm has problem that it return wrong “elements” which include 0… It is not what I like to present here! But when I checked it I found strange behavior which seems to be like Julia’s (0.6.1 and 0.7.0-DEV.0) bug.

If I create array with comprehension then every element include 0:

``````julia> a=[i for i in allSAWs(neigh, 2)]
84-element Array{Array{Int64,1},1}:
[1, 0]
[1, 0]
[1, 0]
[2, 0]
[2, 0]
[2, 0]
[2, 0]
[2, 0]
...

julia> a=[i for i in allSAWs(neigh, 2)];length([i for i in a if 0 in i])==84
true
``````

But if I iterate elements in for loop (or add if statement to comprehension) there are “nonzero” elements too:

``````julia> for i in allSAWs(neigh, 2) println(i);end
[1, 5]
[1, 6]
[1, 0]
[2, 3]
[2, 5]
[2, 6]
[2, 7]
[2, 0]
...

julia> length([i for i in allSAWs(neigh, 2) if 0 in i])==16
true
``````

To get more speed out of the iterator, it returns the paths in the same memory. So, to get an array of all the paths `copy` needs to be used:

``````[copy(i) for i in allSAWs(neigh,2)]
``````

Regarding the zero elements, this is probably a bug, and will post an update soon.

This is not a bug. You always return the same mutable element when iterating over the object.

``````julia> a[1] === a[2]
true
``````

If you don’t want this, you should change the return value of next to be `copy(s[1])`.

The zero elements are generated because of a nasty interaction between `Flatten` and an optimization in `SAWs`. In order to know if the iterator is `done` in a non-mutating way, the `next` function of flatten peeks ahead to another element in the iterator (and leaves the state so `done()` can know if the iterator is done). The same problem is present in `SAWs` and therefore, it also peeks ahead. But for optimization, `SAWs` uses a single vector for the path, and thus has to peek ahead mutatingly inside `done()`. This causes a slip by 1 of the iterator results, which drops the first path and adds the zero terminated path at the end.

This is the explanation.

One workaround is not to use `Flatten` and loop over the starting positions with explicitly. Something like:

``````julia> a=vcat([[copy(i) for i in SAWs(neigh, 2, j)] for j in eachindex(neigh)]...)
84-element Array{Array{Int64,1},1}:
[1, 2]
[1, 5]
⋮
``````

Maybe there is a cleaner workaround, but it still escapes me.

Another, perhaps more general workaround is to redefine `Flatten` to peek into the future in a different way (perhaps slightly less performant). The following code does it:

``````julia> using Base: @propagate_inbounds

julia> import Base: Flatten

julia> @propagate_inbounds function next(f::Flatten, state)
s, inner, s2 = state
while done(inner, s2) && !done(f.it, s)
inner, s = next(f.it, s)
s2 = start(inner)
end
val, s2 = next(inner, s2)
return val, (s, inner, s2)
end
next (generic function with 77 methods)

julia> @inline function done(f::Flatten, state)
s, inner, s2 = state
done(inner, s2) || return false
tmps = copy(s)
while !done(f.it, tmps)
tmps2, tmps = next(f.it, tmps)
done(tmps2, start(tmps2)) || return false
end
return true
end
done (generic function with 64 methods)
``````

With these definitions:

``````for i in allSAWs(neigh, 2) println(i) ; end
``````

works fine.

Thanks! I am glad it is not a bug!

1 Like