JuliaCollections / JuliaCollections/AbstractTrees.jl
StatelessBFS assumes that children are indexable
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 243
- Forks
- 67
- PR merge metrics
- No merged PRs in 30d
Description
Iterating over StatelessBFS calls getindex on the object returned by children():
julia> collect(StatelessBFS(n))
ERROR: MethodError: no method matching getindex(::VectorTreeChildren, ::Int64)
Stacktrace:
[1] getdescendant
@ ~/.julia/packages/AbstractTrees/kBTzE/src/indexing.jl:29 [inlined]
[2] iterate(ti::StatelessBFS{VectorTreeNode}, ind::Vector{Any})
@ AbstractTrees ~/.julia/packages/AbstractTrees/kBTzE/src/iteration.jl:418
As far as I understand, the default for ChildIndexing is NonIndexedChildren, which should imply that it shouldn't be necessary to implement indexing for children? The other iterators (*OrderDFS, Leaves) work fine with my type.
This should work as an MWE:
struct VectorTreeNode
children :: Vector{Any}
VectorTreeNode(cs) = (cs isa Vector) ? new(cs) : new([])
end
struct VectorTreeChildren
node :: VectorTreeNode
end
Base.IteratorSize(::Type{VectorTreeChildren}) = Base.SizeUnknown()
function Base.iterate(it::VectorTreeChildren, state = 1)
if state <= length(it.node.children)
(VectorTreeNode(it.node.children[state]), state + 1)
else
nothing
end
end
using AbstractTrees
AbstractTrees.children(n::VectorTreeNode) = VectorTreeChildren(n)
n = VectorTreeNode([1,[2,3],4])
collect(StatelessBFS(n))
Note: there is also #15 which seems to be a similar issue, but is quite outdated I think -- Leaves works and the indexability trait (ChildIndexing) exists now.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
The failure is in indexing.jl:29, reached from iteration.jl:418; start by reading getdescendant and StatelessBFS iteration alongside ChildIndexing and NonIndexedChildren. Run the supplied VectorTreeNode MWE and verify StatelessBFS can collect non-indexable children without regressing the working DFS and Leaves iterators.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100