NameTree insertion bug

[jlh]

I just found what i think is a bug in the nametree << method :
That code taken from name_tree_spec.rb works ok:

  it "should keep tree balanced when subtree split cascades to root" do
    node = Prawn::NameTree::Node.new(@pdf, 3)
    tree_add(node, ["one", 1], ["two", 2], ["three", 3], ["four", 4])
    tree_add(node, ["five", 5], ["six", 6], ["seven", 7], ["eight", 8])
    tree_dump(node).should == "[[[eight=8,five=5],[four=4,one=1]],[[seven=7,six=6],[three=3,two=2]]]"
  end

but the same code with the values pre-ordered doesn't :

  it "should keep tree balanced when subtree split cascades to root" do
    node = Prawn::NameTree::Node.new(@pdf, 3)
    tree_add(node, ["eight", 8], ["five", 5], ["four", 4,],  ["one",1]
    tree_add(node, ['seven', 7], ['six', 6], ['three', 3], ['two', 2])
    tree_dump(node).should == "[[[eight=8,five=5],[four=4,one=1]],[[seven=7,six=6],[three=3,two=2]]]"
  end

Here is the output :

/usr/lib/ruby/gems/1.9.1/gems/prawn-core-0.5.1/lib/prawn/name_tree.rb:83:in `<<': undefined method `<<' for nil:NilClass (NoMethodError)
        from /usr/lib/ruby/gems/1.9.1/gems/prawn-core-0.5.1/lib/prawn/
name_tree.rb:42:in `add'
        from name_tree_spec.rb:13:in `block in tree_add'
        from name_tree_spec.rb:12:in `each'
        from name_tree_spec.rb:12:in `tree_add'

nametree.rb:83 is "fit << value"
but fit is nil because in the previous line : fit = children.detect { |
child| child >= value }
"child >= value" is always false if the values inserted are already
ordered.

This patch fixes it for me :

diff --git a/lib/prawn/name_tree.rb b/lib/prawn/name_tree.rb
index 267a6e9..c7d20c8 100644
--- a/lib/prawn/name_tree.rb
+++ b/lib/prawn/name_tree.rb
@@ -79,6 +79,7 @@ module Prawn
           split! if children.length > limit
         else
           fit = children.detect { |child| child >= value }
+          fit = children.last unless fit
           fit << value
         end

jlh

[practicingruby]

can we get this in git format-patch format so we can preserve your authorship information?
(or on a fork)

[jlh]

Yes, you can.
I've now created a fork at http://github.com/jlh/prawn and pushed what i hope is a real fix for a real bug.

[practicingruby]

Awesome. We'll look into it soon, and let you know.

[bradediger]

Fixed in 23cafc4. Thanks!