Puzzling bug with yielded array

ruby-talk
1

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

2

A. S. Bradbury wrote:

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.

···

--
Posted via http://www.ruby-forum.com/\.

3

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

···

On Fri, 8 Sep 2006, A. S. Bradbury wrote:
--
what science finds to be nonexistent, we must accept as nonexistent; but what
science merely does not find is a completely different matter... it is quite
clear that there are many, many mysterious things.
- h.h. the 14th dalai lama

4

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: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

5

William Crawford wrote:

A. S. Bradbury wrote:

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.

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

···

--
Posted via http://www.ruby-forum.com/\.

6

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

···

On Friday 08 September 2006 14:51, William Crawford wrote:

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.

7

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

···

On Friday 08 September 2006 14:59, ara.t.howard@noaa.gov wrote:

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--.

8

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

···

On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> wrote:

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?

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

9

Rick Denatale wrote:

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 :slight_smile: 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).

···

On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> wrote:

Rick DeNatale

--
Posted via http://www.ruby-forum.com/\.

10

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

···

On Saturday 09 September 2006 00:46, Eero Saynatkari wrote:

Rick Denatale wrote:
> On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> wrote:
>> 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 :slight_smile: 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

11

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

···

On 9/9/06, A. S. Bradbury <asbradbury@tekcentral.org> wrote:

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.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/