Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Standard API for push_widen! pattern #34478

Open
oxinabox opened this issue Jan 22, 2020 · 4 comments
Open

Standard API for push_widen! pattern #34478

oxinabox opened this issue Jan 22, 2020 · 4 comments
Labels
collections Data structures holding multiple items, e.g. sets feature Indicates new feature / enhancement requests

Comments

@oxinabox
Copy link
Contributor

There is a common pattern for handling not knowing the type of something produced in an iterative fashion, and gathering it up into the smallest container.
Basically you start with the container able something (This bit I think sometimes varies, it could be the first elements eltype, could be result of @default_eltype),
then you get the next thing you want to put in, if it fits then you push it in and continue,
if not then you make a new collection that can hold the union, copy everything over and then repeat.

The core of it is in push_widen! but bits of the setup are in the Set construct, in unique! and in other places

julia/base/array.jl

Lines 681 to 716 in 2d57411

function grow_to!(dest, itr)
y = iterate(itr)
y === nothing && return dest
dest2 = empty(dest, typeof(y[1]))
push!(dest2, y[1])
grow_to!(dest2, itr, y[2])
end
function push_widen(dest, el)
@_inline_meta
new = sizehint!(empty(dest, promote_typejoin(eltype(dest), typeof(el))), length(dest))
if new isa AbstractSet
# TODO: merge back these two branches when copy! is re-enabled for sets/vectors
union!(new, dest)
else
append!(new, dest)
end
push!(new, el)
return new
end
function grow_to!(dest, itr, st)
T = eltype(dest)
y = iterate(itr, st)
while y !== nothing
el, st = y
if el isa T || typeof(el) === T
push!(dest, el::T)
else
new = push_widen(dest, el)
return grow_to!(new, itr, st)
end
y = iterate(itr, st)
end
return dest
end

We should look into a standard and public way to do this.
Its wanted in JuliaCollections/DataStructures.jl#568 (comment)

@non-Jedi
Copy link
Contributor

non-Jedi commented Jan 22, 2020

The other place this pattern is implemented is BangBang.jl just so that people who come across this issue know what options are currently available. There's also been many discussions on discourse wanting a standardized interface for this functionality, e.g.:

(I know there's more not just involving tpapp, but those are what I found with a quick search)

If there was a generic way to expose this as an interface, I think that would be lovely.

@tkf
Copy link
Member

tkf commented Jan 22, 2020

Let me also link some interesting discussions that came up when implementing BangBang interop with other packages (just the ones I remember):

JuliaData/TypedTables.jl#55
JuliaArrays/StructArrays.jl#97
JuliaArrays/StructArrays.jl#100

Also other related issues:

#33495
#24836

Basically you start with the container able something (This bit I think sometimes varies, it could be the first elements eltype, could be result of @default_eltype),

I think it'd be nice to add an interface empty(::Type{T}) where T is a container type. This API must return an instance of container T whose element type is Union{}. This is a useful instance as that's the only type we can safely assume eltype(push_widen!(empty(T), x)) == typeof(x). See also JuliaData/TypedTables.jl#55 (comment) and #34244

@tkf
Copy link
Member

tkf commented Jan 22, 2020

that's the only type

Actually, I think it just has to be an appropriate "bottom" type for the container. It's Union{} for Vector but Pair{Union{}, Union{}} for Dict.

@bramtayl
Copy link
Contributor

Also ref #30076

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
collections Data structures holding multiple items, e.g. sets feature Indicates new feature / enhancement requests
Projects
None yet
Development

No branches or pull requests

5 participants