Puzzling bug with yielded array

[A. S. Bradbury]

I have a Node class, children are stored in a hash with the node's name as the
key and the child node object as the value. I have the method Node#each_level
that yields each level of the node tree as an array:

def each_level(include_self=false)
if include_self
node_queue=[self]
else
node_queue=self.children.values
end
yield node_queue
while node_queue.any? {|node| node.children.empty? == false} do
node_queue.collect! {|node| node.children.values}
node_queue.flatten!
yield node_queue
end
end

Here is the code that demonstrates the problem:

require 'ariel'

root=Ariel::Node.new :root
child1=Ariel::Node.new :child1
child2=Ariel::Node.new :child2
child1_1=Ariel::Node.new :child1_1

root.add_child child1
root.add_child child2
child1.add_child child1_1

results=[]

puts "Results when making an array then flattening it"
root.each_level do |level|
puts "Yielded #{level.inspect}"
puts
raise StandardError unless level.kind_of? Array
results << [level].flatten # works
end

puts "results=#{results.inspect}"
puts

results=[]

puts "Results when just adding the array"
root.each_level do |level|
puts "Yielded #{level.inspect}"
puts
raise StandardError unless level.kind_of? Array
raise StandardError if level.any? {|val| val.kind_of? Array}
results << level # doesn't work
end

puts "results=#{results.inspect}"

I'm really, really stumped. Here's the output:

Results when making an array then flattening it
Yielded [Ariel::Node - node_name=:child1; parent=:root;
children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
children=[];]

Yielded [Ariel::Node - node_name=:child1_1; parent=:child1; children=[];]

results=[[Ariel::Node - node_name=:child1; parent=:root;
children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
children=[];], [Ariel::Node - node_name=:child1_1; parent=:child1;
children=[];]]

Results when just adding the array
Yielded [Ariel::Node - node_name=:child1; parent=:root;
children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
children=[];]

Yielded [Ariel::Node - node_name=:child1_1; parent=:child1; children=[];]

results=[[Ariel::Node - node_name=:child1_1; parent=:child1;
children=[];], [Ariel::Node - node_name=:child1_1; parent=:child1;
children=[];]]

The yielded data is always correct and the same each time, but as you can see
the second results array is wrong. Can anyone explain what's going on here?

Alex

 

[William Crawford]

The yielded data is always correct and the same each time, but as you
can see
the second results array is wrong. Can anyone explain what's going on
here?

Alex

I can't find anything about the 'each_level' method, so I'm guessing
it's in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it's either not doing what you think, or not working
properly.

each_descendant does seem to do what you want, however, in Ariel 0.1.0.

 

[William Crawford]

I can't find anything about the 'each_level' method, so I'm guessing
it's in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it's either not doing what you think, or not working
properly.

each_descendant does seem to do what you want, however, in Ariel 0.1.0.

Wow, totally missed that each_level was yours. -sigh- I really need to
learn to read.

 

[A. S. Bradbury]

I can't find anything about the 'each_level' method, so I'm guessing
it's in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it's either not doing what you think, or not working
properly.

each_descendant does seem to do what you want, however, in Ariel 0.1.0.

Thanks for taking a look. I'm the author of Ariel and I'm working on the next
version, I included my definition of each_level in the previous email. It
actually does seem to be doing exactly what I expect it to - see how the
printed level.inspect is always correct. It's only the results after each
level has been appended to the array that is wrong.

By the way, if you're reading this via ruby-forum (which it seems you are),
ruby-forum.com has eaten most of my pasted output. See the full post at
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/213339

Regards,
Alex

 

[ara.t.howard]

I have a Node class, children are stored in a hash with the node's name as the
key and the child node object as the value. I have the method Node#each_level
that yields each level of the node tree as an array:

def each_level(include_self=false)
if include_self
node_queue=[self]
else
node_queue=self.children.values
end
yield node_queue
while node_queue.any? {|node| node.children.empty? == false} do
node_queue.collect! {|node| node.children.values}
node_queue.flatten!
yield node_queue
end
end

the problem is here. this illustrates the issue:

harp:~ > cat a.rb
def yields_shared_then_munged_list
list = %w[ forty-two ]
yield list
list.collect!{|elem| elem.upcase}
yield list
end

yields_shared_then_munged_list{|list| p list}


harp:~ > ruby a.rb
["forty-two"]
["FORTY-TWO"]

your method first returns a list to the caller but, later, munges it in place
without the caller's consent. this is as evil as returning pointer to member
in c--.

Here is the code that demonstrates the problem:

require 'ariel'

root=Ariel::Node.new :root
child1=Ariel::Node.new :child1
child2=Ariel::Node.new :child2
child1_1=Ariel::Node.new :child1_1

root.add_child child1
root.add_child child2
child1.add_child child1_1

results=[]

puts "Results when making an array then flattening it"
root.each_level do |level|
puts "Yielded #{level.inspect}"
puts
raise StandardError unless level.kind_of? Array
results << [level].flatten # works

because you are making a copy. so the traversal code does fubar the elements
of results in place.

end

puts "results=#{results.inspect}"
puts

results=[]

puts "Results when just adding the array"
root.each_level do |level|
puts "Yielded #{level.inspect}"
puts
raise StandardError unless level.kind_of? Array
raise StandardError if level.any? {|val| val.kind_of? Array}
results << level # doesn't work

because results contains a reference to the yielded array (not a copy) so the
subsequent calls to 'collect!', etc. scramble it in place.


kind regards.


-a

 

[Michael Ulm]

A. S. Bradbury wrote:

--snip--

results << level # doesn't work

results << level.dup


HTH,

Michael

--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: (e-mail address removed)
Visit our Website: www.isis-papyrus.com

 

[A. S. Bradbury]

your method first returns a list to the caller but, later, munges it in
place without the caller's consent. this is as evil as returning pointer
to member in c--.

I really appreciate your detailed reply, the problem is very clear now and
hopefully I've learnt from it.

A more general question - how would you (ruby-talk readers) implement this
method? Two people on #ruby-lang suggested I make it recursive, but I really
don't see this sort of tree traversal mapping to a recursive method, am I
wrong?

Alex

 

[Rick DeNatale]

A more general question - how would you (ruby-talk readers) implement this
method? Two people on #ruby-lang suggested I make it recursive, but I really
don't see this sort of tree traversal mapping to a recursive method, am I
wrong?

Tree traversal usually lends itself well to a recursive
implementation, but it's not clear to me exactly what your each_level
method is supposed to do.


But here's a recursive implementation that might do the same thing.

def each_level(include_self=false, &block)
yield [self] if include_self
kids = children.values
unless kids.empty?
yield kids
kids.each do {|kid| kid.each_level(&block)}
end
end

 

[Eero Saynatkari]

A more general question - how would you (ruby-talk readers) implement this
method? Two people on #ruby-lang suggested I make it recursive, but I really
don't see this sort of tree traversal mapping to a recursive method, am I
wrong?

Tree traversal usually lends itself well to a recursive
implementation, but it's not clear to me exactly what your each_level
method is supposed to do.


But here's a recursive implementation that might do the same thing.

def each_level(include_self=false, &block)
yield [self] if include_self
kids = children.values
unless kids.empty?
yield kids
kids.each do {|kid| kid.each_level(&block)}
end
end

That is a semi-depth-first traversal, though. Apparently
we are looking for breadth-first here That would be
simplest to implement with some kind of a storage--say
an Array with an element for each level--which is sort
of what the OP's method was doing (though only for the
first three levels since it does not recurse).

 

[A. S. Bradbury]

A more general question - how would you (ruby-talk readers) implement
this method? Two people on #ruby-lang suggested I make it recursive, but
I really don't see this sort of tree traversal mapping to a recursive
method, am I wrong?

Tree traversal usually lends itself well to a recursive
implementation, but it's not clear to me exactly what your each_level
method is supposed to do.


But here's a recursive implementation that might do the same thing.

def each_level(include_self=false, &block)
yield [self] if include_self
kids = children.values
unless kids.empty?
yield kids
kids.each do {|kid| kid.each_level(&block)}
end
end

That is a semi-depth-first traversal, though. Apparently
we are looking for breadth-first here That would be
simplest to implement with some kind of a storage--say
an Array with an element for each level--which is sort
of what the OP's method was doing (though only for the
first three levels since it does not recurse).

Rick DeNatale

Indeed, I am implementing a breadth-first or level-by-level traversal. I don't
understand your comment about "only for the first three levels"?

I can see other forms of tree traversal lending themselves well to a recursive
implementation, but not really level by level, particular as I want each
level to be returned as an array.

Alex

 

[Rick DeNatale]

I can see other forms of tree traversal lending themselves well to a recursive
implementation, but not really level by level, particular as I want each
level to be returned as an array.

Here's a recursive implementation of that then:

def each_level(include_self=false, levels=[[]], depth=0)
levels[depth] << self if include_self
kids = self.children.values
unless kids.empty?
levels << [] unless levels.length > depth + 1
kids.each {|kid| kid.each_level(true, levels, depth+1)}
end
levels.each {|l| yield l} if depth.zero?
end

Although it might be better to make a public wrapper method to start,
and make the internal recursive method private, so as not to expose
the extra parameters:

def each_level(include_self=false)
levels = []
levels << [self] if include_self
kids = self.children.values
unless kids.empty?
levels << []
kids.each {|kid| kid.each_level_internal(levels, 1)}
end
levels.each {|l| yield l}
end

private
def each_level_internal(levels, depth)
levels[depth] << self
kids = self.children.values
unless kids.empty?
levels << [] unless levels.length > depth + 1
kids.each {|kid|
kid.each_level_internal(levels, depth+1)}
end
end