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.

Sign up for GitHub

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

Jump to bottom

Partition() w/ size greater than the length of the input does not work #528

Closed
LebedevRI opened this issue Jun 17, 2022 · 0 comments · Fixed by #529
Closed

Partition() w/ size greater than the length of the input does not work #528

LebedevRI opened this issue Jun 17, 2022 · 0 comments · Fixed by #529

Comments

@LebedevRI
Copy link
Contributor

LebedevRI commented Jun 17, 2022 •
edited
Loading 

using Transducers
1:4 |> Partition(5; flush=true) |> Map(copy) |> collect

BoundsError: attempt to access 4-element Vector{Int64} at index [4:8]

Stacktrace:
  [1] throw_boundserror(A::Vector{Int64}, I::Tuple{UnitRange{Int64}})
    @ Base ./abstractarray.jl:703
  [2] checkbounds
    @ ./abstractarray.jl:668 [inlined]
  [3] view
    @ ./subarray.jl:177 [inlined]
  [4] complete(rf::Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Int64}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}})
    @ Transducers ~/.julia/packages/Transducers/HBMTc/src/library.jl:907
  [5] _foldl_linear_bulk
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:201 [inlined]
  [6] macro expansion
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:192 [inlined]
  [7] macro expansion
    @ ~/.julia/packages/Transducers/HBMTc/src/basics.jl:117 [inlined]
  [8] _foldl_array
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:188 [inlined]
  [9] __foldl__
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:182 [inlined]
 [10] #transduce#142
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:523 [inlined]
 [11] transduce
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:512 [inlined]
 [12] transduce(xform::Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Map{Type{BangBang.NoBang.SingletonVector}}}}, f::Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}, init::BangBang.SafeCollector{Empty{Vector{Union{}}}}, coll::UnitRange{Int64}; kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ Transducers ~/.julia/packages/Transducers/HBMTc/src/processes.jl:506
 [13] transduce
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:504 [inlined]
 [14] collect(xf::Transducers.Composition{Partition, Map{typeof(copy)}}, coll::UnitRange{Int64})
    @ Transducers ~/.julia/packages/Transducers/HBMTc/src/processes.jl:807
 [15] collect
    @ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:821 [inlined]
 [16] |>(x::Transducers.Eduction{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.BottomRF{Completing{typeof(push!!)}}}}, UnitRange{Int64}}, f::typeof(collect))
    @ Base ./operators.jl:911
 [17] top-level scope
    @ In[8]:2
 [18] eval
    @ ./boot.jl:368 [inlined]
 [19] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)
    @ Base ./loading.jl:1299
Orig If we start with ``` using Transducers

1:32 |> Partition(5; flush=true) |> Map(copy) |> Partition(5; flush=true) |> Map(copy) |> collect

we get

2-element Vector{Vector{Vector{Int64}}}:
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
[[26, 27, 28, 29, 30], [31, 32]]

... which is as expected.

But if we add one more step:

using Transducers

1:32 |> Partition(5; flush=true) |> Map(copy) |> Partition(5; flush=true) |> Map(copy) |> Partition(5; flush=true) |> Map(copy) |> collect

i'd expect to get

1-element Vector{Vector{Vector{Vector{Int64}}}}:
[[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]], [[26, 27, 28, 29, 30], [31, 32]]]


Yet we suddenly get

BoundsError: attempt to access 2-element Vector{Vector{Vector{Int64}}} at index [2:6]

Stacktrace:
[1] throw_boundserror(A::Vector{Vector{Vector{Int64}}}, I::Tuple{UnitRange{Int64}})
@ Base ./abstractarray.jl:703
[2] checkbounds
@ ./abstractarray.jl:668 [inlined]
[3] view
@ ./subarray.jl:177 [inlined]
[4] complete(rf::Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Vector{Vector{Int64}}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/library.jl:907
[5] complete(rf::Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Vector{Vector{Int64}}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/core.jl:546
[6] complete(rf::Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}, Tuple{Int64, Int64, Vector{Vector{Int64}}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Vector{Vector{Int64}}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/library.jl:912
[7] complete(rf::Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}, Tuple{Int64, Int64, Vector{Vector{Int64}}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Vector{Vector{Int64}}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/core.jl:546
[8] complete(rf::Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}}}, result::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}}}, Tuple{Int64, Int64, Vector{Int64}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}, Tuple{Int64, Int64, Vector{Vector{Int64}}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Vector{Vector{Int64}}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/library.jl:912
[9] _foldl_linear_bulk(rf::Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}}}, acc::Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}}}, Tuple{Int64, Int64, Vector{Int64}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}}}, Tuple{Int64, Int64, Vector{Union{}}}, Transducers.PrivateState{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}}, Tuple{Int64, Int64, Vector{Union{}}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}}}}, arr::UnitRange{Int64}, i0::Int64)
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/processes.jl:201
[10] macro expansion
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:192 [inlined]
[11] macro expansion
@ ~/.julia/packages/Transducers/HBMTc/src/basics.jl:117 [inlined]
[12] _foldl_array
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:188 [inlined]
[13] foldl
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:182 [inlined]
[14] #transduce#142
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:523 [inlined]
[15] transduce
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:512 [inlined]
[16] transduce(xform::Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Map{Type{BangBang.NoBang.SingletonVector}}}}}}}}, f::Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}, init::BangBang.SafeCollector{Empty{Vector{Union{}}}}, coll::UnitRange{Int64}; kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/processes.jl:506
[17] transduce
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:504 [inlined]
[18] collect(xf::Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Transducers.Composition{Partition, Transducers.Composition{Map{typeof(copy)}, Transducers.Composition{Partition, Map{typeof(copy)}}}}}}, coll::UnitRange{Int64})
@ Transducers ~/.julia/packages/Transducers/HBMTc/src/processes.jl:807
[19] collect
@ ~/.julia/packages/Transducers/HBMTc/src/processes.jl:821 [inlined]
[20] |>(x::Transducers.Eduction{Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.Reduction{Partition, Transducers.Reduction{Map{typeof(copy)}, Transducers.BottomRF{Completing{typeof(push!!)}}}}}}}}, UnitRange{Int64}}, f::typeof(collect))
@ Base ./operators.jl:911
[21] top-level scope
@ In[34]:3
[22] eval
@ ./boot.jl:368 [inlined]
[23] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)
@ Base ./loading.jl:1299

</details>

This is julia 1.8.0-rc1+git, and up-to-date packages.
@LebedevRI LebedevRI changed the title Partition(flush=true) sometimes results in BoundsError Partition() w/ size greater than the length of the input does not work Jun 17, 2022
LebedevRI added a commit to LebedevRI/Transducers.jl that referenced this issue Jun 23, 2022
@LebedevRI
Fix Partition() w/ size greater than the length of the input
ca1a678 
`complete()` only worked correctly if at least a single full partition
has been produced already, otherwise the `buf` would be smaller
than the `xform(rf).size`, and we get buffer overflow, etc.

I've added sufficient test coverage for the issue, that now passes.

I have stumbled into this while trying to write a reduction tree,
not sure if this is something that might be interesting here?

Fixes JuliaFolds#528
LebedevRI added a commit to LebedevRI/Transducers.jl that referenced this issue Jun 23, 2022
@LebedevRI
Fix Partition() w/ size greater than the length of the input
6245a2a 
`complete()` only worked correctly if at least a single full partition
has been produced already, otherwise the `buf` would be smaller
than the `xform(rf).size`, and we get buffer overflow, etc.

I've added sufficient test coverage for the issue, that now passes.

I have stumbled into this while trying to write a reduction tree,
not sure if this is something that might be interesting here?

Fixes JuliaFolds#528
@LebedevRI LebedevRI mentioned this issue Jun 23, 2022
Merged
LebedevRI added a commit to LebedevRI/Transducers.jl that referenced this issue Nov 25, 2022
@LebedevRI
Fix Partition() w/ size greater than the length of the input
2bf2e55 
`complete()` only worked correctly if at least a single full partition
has been produced already, otherwise the `buf` would be smaller
than the `xform(rf).size`, and we get buffer overflow, etc.

I've added sufficient test coverage for the issue, that now passes.

I have stumbled into this while trying to write a reduction tree,
not sure if this is something that might be interesting here?

Fixes JuliaFolds#528
MasonProtter pushed a commit that referenced this issue Nov 25, 2022
@LebedevRI
Fix Partition() w/ size greater than the length of the input (#529)
477d8af 
`complete()` only worked correctly if at least a single full partition
has been produced already, otherwise the `buf` would be smaller
than the `xform(rf).size`, and we get buffer overflow, etc.

I've added sufficient test coverage for the issue, that now passes.

I have stumbled into this while trying to write a reduction tree,
not sure if this is something that might be interesting here?

Fixes #528
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix Partition() w/ size greater than the length of the input LebedevRI/Transducers.jl
1 participant
@LebedevRI