possible bug in Trie - value is corrupted

[stevegoobermanhill]

Hi,
Possible bug in fast-trie. It looks like the node value is becoming corrupted in some circumstances.

Here is a test script to demonstrate the bug. The underlying idea is that since the Trie holds key, value pairs, we use the value to hold an array of indexes to the keys. The problem is that the value appears to get corrupted at random points, but reproducibly. Could the GC be involved?

Here is a script which demonstrates the problem. I'm using MRI 2.3.0p0.

[Note] Code edited - revised version with a rescue clause always segfaults

Thanks

Steve

#!/usr/local/bin/ruby
require 'trie'

#test for possible bug in fast-trie
#the idea is that each value in the trie is an array
#that we will use to hold data about the elements of the trie
#in this case the elements of the trie are words, and
#each data element is an index


trie=Trie.new

(1..100000).each  do |n|
   #puts n
   
   #limited set of random strings
   str = [1,1,2,2,3,3,4,4].shuffle.join.squeeze
   
   #v (the value) should be nil or an Array
   v = trie.get(str)
   if v
      begin
         v << n #dies here because v is not an Array. Why?
      rescue
         STDERR.puts  [str, v.class, v].join('|')
      end
   else
      trie.add(str, [n]) #add a new element to the trie with Array value
   end
end

[mmmries]

I have seen this same behavior. Storing hashes or lists as the values seems to exhibit this behavior.