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

Should prevent loop when creating tree and provide proper error message #5

Closed
leomao10 opened this Issue Apr 13, 2012 · 1 comment

Comments

Projects
None yet
2 participants
@leomao10

leomao10 commented Apr 13, 2012

Just try this code by mistake:

node = Tree::TreeNode.new("Root")
node << node

And it throw following exception:

SystemStackError: stack level too deep
    from /Users/leo.liang/.rvm/gems/ruby-1.9.3-p125@des_scorecard/gems/rubytree-0.8.2/lib/tree.rb:508

As it try to output node in irb.

It maybe better to check the input data and prevent user to change node if they add children node that may cause loop.

@ghost ghost assigned evolve75 Aug 19, 2012

@evolve75

This comment has been minimized.

Show comment
Hide comment
@evolve75

evolve75 Aug 19, 2012

Owner

Thanks for highlighting the error.

I have added a check to prevent the scenario pointed out by your sample code, and the fix will be available in 0.8.3.

However, the possibility exists that a node which has already been added to the tree can get added again further down the hierarchy, and this is a somewhat different problem to solve. We could check every single addition against the tree, but this will be a big performance hit for large trees.
An alternative could be to maintain a registry of all known nodes (as a hash in the root), but this does require a good analysis of the code across multiple paths, as detaching sub-trees, or merging in new trees become considerably performance intensive, as the registry will need rebuilding in both scenarios.

The question is really about performance, and since RubyTree is meant for generic usage, it needs to be balanced appropriately.

Owner

evolve75 commented Aug 19, 2012

Thanks for highlighting the error.

I have added a check to prevent the scenario pointed out by your sample code, and the fix will be available in 0.8.3.

However, the possibility exists that a node which has already been added to the tree can get added again further down the hierarchy, and this is a somewhat different problem to solve. We could check every single addition against the tree, but this will be a big performance hit for large trees.
An alternative could be to maintain a registry of all known nodes (as a hash in the root), but this does require a good analysis of the code across multiple paths, as detaching sub-trees, or merging in new trees become considerably performance intensive, as the registry will need rebuilding in both scenarios.

The question is really about performance, and since RubyTree is meant for generic usage, it needs to be balanced appropriately.

@evolve75 evolve75 closed this Dec 24, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment