JuliaCollections / JuliaCollections/AbstractTrees.jl

StatelessBFS assumes that children are indexable

Open
#113 1 comment 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.