Recursive methods crash in Fiber/Thread due to stack size

[evnu]

RubyTree uses recursion for methods such as each and detached_subtree_copy. This is ok for smaller well-balanced trees, but fails for unbalanced trees when Fiber or Threads are involved.

Constructing and Walking a Linear Tree

See the following example method to construct a linear tree:

#!/usr/bin/ruby
require "tree"

def run_test(depth=100)
    tree = Tree::TreeNode.new("/")
    current = tree
    depth.times do |i|
        new_node = Tree::TreeNode.new("#{i}")
        current << new_node
        current = new_node
    end
    tree.each{|n| nil}
end

This runs fine when executed in the main thread...

puts "Run test in the main thread"
run_test()

...but fails when a Fiber or Thread is involved:

puts "Run test in a fiber"
begin
    Fiber.new do
        run_test()
    end.resume
rescue SystemStackError
    puts "Fiber died."
end

puts "Run test in a thread"
begin
    Thread.abort_on_exception = true
    Thread.new do
        run_test(600) # 600 is not chosen arbitrary: this is the first number where it fails here.
    end
    sleep(3)
rescue SystemStackError
    puts "Thread died."
end

Note that the recursion depth between Fiber and Thread differs.

Demo Output

The example script above produces the following output with my machine:

% ./example.rb
Run test in the main thread
Run test in a fiber
Fiber died.
Run test in a thread
Thread died.

Possible Solution

This should be resolvable by replacing the recursion in each, detached_subtree_copy and elsewhere with the respective iterative representation. each could possibly be fixed like this:

module Tree
    class TreeNode
        def each(&blk)
            expand_nodes = [self]
            while expand_nodes != []
                current = expand_nodes.shift
                yield current
                expand_nodes = current.children.concat(expand_nodes)
            end
        end
    end

[evolve75]

Magnus,

Thank you for highlighting this. I was actually planning to replace recursions at some point of time. I will review the issue and put in a few test cases to start with.

Just out of curiosity, would you be able to share the use case where you need this large volume of nodes?

Anupam

[evnu]

We are using rubytree to display different kinds of taxonomies. The graphs are built using user input and sometimes users create very long branches (probably by accident). We will eventually filter those branches, but for that we have to find them first. Note that the example above is quite artificial; if the node names are longer, it should crash with a smaller depth. We had one case where it crashed for a tree of depth 40.

[evolve75]

Fix is working fine, and will be available in R0.9.0.