Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

searching nested structures

by IOrdy (Friar)
on Jan 05, 2004 at 01:23 UTC ( #318738=perlquestion: print w/replies, xml ) Need Help??

IOrdy has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to search a nested structure and return an array with references to all occurrences that match something like:
->{foo}->{bar} or ->{foo}->[0]->{bar}
My recursive function (below) works fine for single instances like ->{bar} but somehow creates an endless loop with multiple parts (i.e ->{foo}->{bar}).
I think it has something to do with the eval corrupting $data but I dont understand why or how to fix it.

Any help would be appreciated.

The function:
sub rec_data { my $path = shift; # ->{foo}->{bar} my $data = shift; # nested perl structure my @results; # nothing to search return unless ref $data; # stop the evals complaining no warnings 'all'; if (ref $data eq 'HASH') { foreach my $k (keys %$data) { my $ref = qq|\$data->{$k}$path|; if (my $val = eval($ref)) { push @results, ref($val) ? $val : eval "\\$ref"; } if (ref $data->{$k}) { push @results, rec_data($path, $data->{$k}); } } } elsif (ref $data eq 'ARRAY') { foreach my $k (@$data) { my $ref = qq|\$k$path|; if (my $val = eval($ref)) { push @results, ref($val) ? $val : eval "\\$ref"; } if (ref $k) { push @results, rec_data($path, $k); } } } return @results; } # test data my $data = { test => { foo => { bar => 'bar', baz => 'baz' }, bar => { baz => 'baz' }, } } # search my @results = rec_data('->{foo}->{bar}', $data);

Replies are listed 'Best First'.
Re: searching nested structures
by pg (Canon) on Jan 05, 2004 at 04:31 UTC

    Autovivification!

    When you search for a path, if its depth is greater than 1, your main data under search will grow, and that's exactly why your program will not stop.

    Now I think it is your duty to fix it.

    I added some debug info at certain key points, to reveal that your data is growing itself, see my inline comments: (Run it and watch the chain of foo->{foo}->{foo}->...->{})

    use Data::Dumper; sub rec_data { my $path = shift; # ->{foo}->{bar} my $data = shift; # nested perl structure my $data_main = shift; print Dumper($data_main);#let's see the fact my @results; # nothing to search return unless ref $data; # stop the evals complaining no warnings 'all'; if (ref $data eq 'HASH') { foreach my $k (keys %$data) { my $ref = qq|\$data->{$k}$path|; if (my $val = eval($ref)) { push @results, ref($val) ? $val : eval "\\$ref"; } if (ref $data->{$k}) { print "calling from entry point1, k = $k\n"; push @results, rec_data($path, $data->{$k}, $data_main +);#just pass the third parameter along without change(?) } } } elsif (ref $data eq 'ARRAY') { foreach my $k (@$data) { my $ref = qq|\$k$path|; if (my $val = eval($ref)) { push @results, ref($val) ? $val : eval "\\$ref"; } if (ref $k) { print "calling from entry point2\n"; push @results, rec_data($path, $k, $data_main); } } } return @results; } my $data_main = { test => { foo => { bar => 'bar', baz => 'baz' }, bar => { baz => 'baz' } , } }; my @results = rec_data('->{foo}->{bar}', $data_main, $data_main);#The +program should never change the third parameter, is that true? print Dumper(\@results);
Re: searching nested structures
by exussum0 (Vicar) on Jan 05, 2004 at 02:12 UTC
    Update: It's the eval as roger implicitly pointed out in his reply as well. Time to be explicit. From man perlfunc on exists

    Given an expression that specifies a hash element or array ele- ment, returns true if the specified element in the hash or array has ever been initialized, even if the corresponding value is undefined. The element is not autovivified if it doesn't exist.

    You are autovifying.


    You can see this by modifying your code as such.. (use Data::Dumper)
    . . . print "----\n"; print Dumper $data; my $ref = qq|\$data->{$k}$path|; print "String: $ref\n"; if (my $val = eval($ref)) { push @results, ref($val) ? $val : eval "\\$ref"; } if (exists $data->{$k}) { print Dumper $data; push @results, rec_data($path, $data->{$k}); . . .
    Your eval is creating the a-formentioned structure. You may wanna break down your search structure in a different way.
    Here's the output from above. You are creating a circular reference.
    $VAR1 = { 'foo' => { 'baz' => 'baz', 'bar' => 'bar' }, 'bar' => { 'baz' => 'baz' } }; String: $data->{foo}->{foo}->{bar} $VAR1 = { 'foo' => { 'foo' => {}, 'baz' => 'baz', 'bar' => 'bar' }, 'bar' => { 'baz' => 'baz' } };

    Play that funky music white boy..

      add on top of what sporty quoted, exists() is just one case for autovivification. To be precise on autovivification: any attempt to read or test an element that does not exist, will create its ancestors.

      use Data::Dumper; use strict; use warnings; my $data = {"a" => 1}; $data->{"b"}->{"b"}->{"b"}->{"b"};#useless use of hash element in void + context? interesting error message. The useless use is actually not +that useless. print Dumper($data);

      this prints:

      $VAR1 = { 'a' => 1, 'b' => { 'b' => { 'b' => {} } } };
Re: searching nested structures
by Roger (Parson) on Jan 05, 2004 at 03:34 UTC
    use strict; use warnings; use Data::Dumper; # test data my $data = { test => { foo => { bar => 'bar', baz => 'baz', bul => { foo => { bar => 'bul' } } }, bar => { baz => 'baz' }, }, foo => { bar => 'foo' }, }; my $found = rec_data('->{foo}->{bar}', $data); print Dumper($found); print "--- array of ref's ---\n"; print "$_\n" for @$found; # verify by hand print "--- verify by hand ---\n"; print \$data->{foo}->{bar}, "\n", \$data->{test}->{foo}->{bar}, "\n", \$data->{test}->{foo}->{bul}->{foo}->{bar}, "\n"; sub rec_data { my ($pattern, $data) = @_; return if ref($data) ne 'HASH'; my @keys = keys %$data; # persist the value of the keys return if !@keys; my @found; # do we see pattern? if (eval 'exists $data' . $pattern) { push @found, eval '\$data' . $pattern; } # traverse the 'children' # foreach (keys %$data) will not work and will result # in deep recursion foreach (@keys) { # get the value of each key my $result = rec_data($pattern, $data->{$_}); next if ! $result; push @found, @$result; } return(\@found); }
    And the output is -
    $VAR1 = [ \'foo', \'bar', \'bul' ]; --- array of ref's --- SCALAR(0x167bdc) SCALAR(0x167b4c) SCALAR(0xf4a50) --- verify by hand --- SCALAR(0x167bdc) SCALAR(0x167b4c) SCALAR(0xf4a50)
Re: searching nested structures
by Anonymous Monk on Jan 05, 2004 at 05:49 UTC

    One way to deal with autovivification is copying:

    use Storable qw/dclone/; my $data = { test => { foo => { bar => 'bar', baz => 'baz', bul => { foo => { bar => 'bul' } } }, bar => { baz => 'baz' }, }, foo => { bar => 'foo' }, bar => [1,2,{foo => {bar => 42}},3] }; my @result = rec_data('->{foo}->{bar}',$data); print join(':',@result),"\n"; sub rec_data { my $path = shift; my $data = shift; my $ref = ref $data || return; my @vals = $ref eq 'HASH' ? values %$data : @$data; my $cdat = dclone($data); return (eval"\$cdat$path" || (),map{rec_data($path,$_)}@vals) }
Re: searching nested structures
by IOrdy (Friar) on Jan 05, 2004 at 05:13 UTC
    Thanks all, I can see whats going on now and I understand why it's happening but I'm still at a loss as how to avoid autovivification without breaking up the origional pattern into parts and testing them one at a time.

    Roger: Because 'exists' still wont stop autovivification your solution above will still muddy the origional structure (If you Dumper($data) after searching you can see empty foo => {}'s everywhere.)

    Update: For future reference I found this article(perlarchive.com) which had an example sub to get me started on testing deep structures without triggering autovivification.

      Unfortunately, you have to control this yourself.

      To avoid unwanted autovivification, before read/test an element, always first make sure the existance of all its ancestors. That "all" in bold is automatically guranteed, if your checking is start from the oldest ancestor, and stops at the first sight of a non-exist ancestor.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://318738]
Approved by Enlil
Front-paged by PERLscienceman
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2023-02-06 20:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (36 votes). Check out past polls.

    Notices?