Walking a Nested Structure

Part I · Module 7 · Chapter 7.10 · Walking a Nested Structure

1. Three Questions, One Function

Any node in a Perl structure is one of three things: a hash reference, an array reference, or a plain value. ref() tells you which — Chapter 7.14 covers it properly, and here it is simply the dispatch key.

use strict;
use warnings;

my $design = {
    blocks => ["alu", "fifo"],
    limits => { retries => 3, timeout => 45 },
    matrix => [ [1, 2], [3] ],
    name   => "top",
};

sub walk {
    my ($node, $path) = @_;
    my $kind = ref $node;

    if ($kind eq "HASH") {
        walk($node->{$_}, $path . "{$_}") for sort keys %$node;
    }
    elsif ($kind eq "ARRAY") {
        walk($node->[$_], $path . "[$_]") for 0 .. $#$node;
    }
    elsif ($kind eq "") {
        printf "%-28s = %s\n", $path, (defined $node ? $node : "undef");
    }
    else {
        printf "%-28s = <%s reference>\n", $path, $kind;
    }
}

walk($design, 'design');

design{blocks}[0]            = alu
design{blocks}[1]            = fifo
design{limits}{retries}      = 3
design{limits}{timeout}      = 45
design{matrix}[0][0]         = 1
design{matrix}[0][1]         = 2
design{matrix}[1][0]         = 3
design{name}                 = top

Every leaf, with the exact expression that reaches it. You could paste any of those paths into a program and it would work.

The function is twenty lines and the structure of it is worth naming:

• ref $node is the dispatch. "HASH", "ARRAY", or "" for a plain value.
• The two container branches recurse, each extending the path with the step it took.
• "" is the base case — a plain value, printed. Without a base case the recursion would not terminate.
• The else catches everything else — a code reference, a Regexp, a blessed object. Printing what it is rather than ignoring it means the walker never silently drops data, which matters when you are using it to find out what you have.

Note $path . "[$_]" and $path . "{$_}" are built with concatenation, not interpolation. That is deliberate and §4 is the reason.

Note also sort keys %$node in the hash branch. Without it the output order varies between runs, as Chapter 6.5 established. A walker you intend to diff — against an earlier run, or against a known-good dump — needs the sort.

2. Ragged and Uneven Shapes Need No Extra Code

Look at the input again. blocks is a flat list; limits is a hash; matrix is a list of lists with rows of different lengths; name is a bare string at the top level alongside three references.

The walker handled all four without a single special case, because it never assumes anything about depth or uniformity — it asks each node what it is and acts. That is the property that makes this technique worth the recursion: the code does not grow when the data gets more complicated.

Pointed at a deliberately awkward structure — ragged rows, an empty array, an undef, and a code reference — the same unmodified walker gives:

my $d = {
    matrix  => [ [1,2], [3] ],
    empty   => [],
    nothing => undef,
    code    => sub { 1 },
};

d{code}                  = <CODE reference>
d{matrix}[0][0]          = 1
d{matrix}[0][1]          = 2
d{matrix}[1][0]          = 3
d{nothing}               = undef

Four of the five keys are accounted for. undef printed as undef, the code reference was reported by the else branch rather than dropped, and the ragged rows needed nothing.

empty produced no line at all. Its value is a real array reference holding nothing, so the ARRAY branch ran and 0 .. $#$node was 0 .. -1 — an empty range, so no recursive call happened and no leaf was reached. That is worth knowing because it means a walker's output cannot distinguish a key that is absent from a key holding an empty container. If that distinction matters, print something in the container branch when it has no children.

3. Summarising Instead of Printing

The same skeleton with a different base case answers questions about a structure rather than listing it.

use strict;
use warnings;

my $design = {
    blocks => ["alu", "fifo"],
    limits => { retries => 3, timeout => 45 },
    matrix => [ [1, 2], [3] ],
    name   => "top",
};

my %tally;

sub visit {
    my ($node) = @_;
    my $kind = ref($node) || "scalar";
    $tally{$kind}++;
    if    (ref $node eq "HASH")  { visit($_) for map { $node->{$_} } sort keys %$node }
    elsif (ref $node eq "ARRAY") { visit($_) for @$node }
}

visit($design);

printf "%-8s %d\n", $_, $tally{$_} for sort keys %tally;

sub depth {
    my ($node) = @_;
    return 0 unless ref $node;
    my @kids = ref $node eq "HASH" ? values %$node : ref $node eq "ARRAY" ? @$node : ();
    my $max = 0;
    for my $k (@kids) { my $d = depth($k); $max = $d if $d > $max }
    return 1 + $max;
}
printf "max depth: %d\n", depth($design);

ARRAY    4
HASH     2
scalar   8
max depth: 3

Two useful walkers in one file.

visit counts nodes by kind. Four arrays — blocks, matrix, and matrix's two rows. Two hashes — the top level and limits. Eight scalars: two block names, two limits, three matrix cells, and name.

depth returns the deepest nesting. It is the standard recursive maximum: a plain value is depth 0, and a container is one more than the deepest of its children. max depth: 3 is the design → matrix → row → cell path.

Note ref($node) || "scalar" for the tally key. ref() on a plain value returns the empty string, which is a legal hash key but a confusing one to read in output, so || substitutes a word. That is a legitimate use of || rather than // — the empty string is exactly what you want to replace here, and it is false.

4. The Trap: Building the Path String

This is the bug I hit writing §1's walker, and it is worth the space because the diagnosis is not obvious.

The natural way to extend the path is interpolation:

walk($node->{$k}, "$path{$k}");

Global symbol "%path" requires explicit package name (did you forget to declare "my %path"?) at walk.pl line 17.
Execution of walk.pl aborted due to compilation errors.

255

The error names %path — a hash that does not exist. Inside a double-quoted string, "$path{$k}" is not "$path, then a brace"; it is the hash element $path{$k} of %path. Perl's interpolation rules consume the braces as a subscript.

The array form fails the same way:

Global symbol "@path" requires explicit package name (did you forget to declare "my @path"?) at -e line 1.

This is exactly the same root cause as Chapter 7.4 §3's mandatory first arrow: $path, @path and %path are three unrelated variables that happen to share a name, and a subscript after $path selects one of the other two. Here it arrives disguised as a string-formatting problem.

The fix is concatenation:

walk($node->{$_}, $path . "{$_}") for sort keys %$node;

[design{blocks}]

5. Guarding the Recursion

Two practical limits are worth knowing before you point a walker at real data.

A structure that refers to itself will not terminate. Chapter 7.2 §3 mentioned cycles as a reference-counting consideration; here they are a recursion consideration:

my $node = { name => "a" };
$node->{self} = $node;         # refers to itself

A naive walker follows self forever. Measured, with a counter added to abort at 500 visits so the run terminates:

Deep recursion on subroutine "main::walk" at cycle-naive.pl line 14.
Deep recursion on subroutine "main::walk" at cycle-naive.pl line 14.
ABORT: 500 visits reached

255

Deep recursion on subroutine "main::walk" is the exact warning, emitted at 100 levels. Note that it is a warning — the program kept going, and without the artificial abort it would have continued until it exhausted memory. Two warnings appeared before the counter stopped it.

The defence is to remember what you have visited, keyed on the reference's own string form — which Chapter 7.1 §5 showed is unique per container:

use strict;
use warnings;

my $node = { name => "a" };
$node->{self} = $node;

my @leaves;

sub walk {
    my ($n, $path, $seen) = @_;
    $seen ||= {};
    if (ref $n) {
        return if $seen->{ "$n" }++;        # already been here
    }
    if (ref $n eq "HASH") {
        walk($n->{$_}, $path . "{$_}", $seen) for sort keys %$n;
    }
    elsif (ref $n eq "") {
        push @leaves, "$path = " . (defined $n ? $n : "undef");
    }
}

walk($node, 'n');
printf "terminated. %d leaf/leaves:\n", scalar(@leaves);
print "  $_\n" for @leaves;

terminated. 1 leaf/leaves:
  n{name} = a

0

It terminates, finds the one real leaf, and visits the self-reference exactly once before returning. $seen->{"$n"}++ uses the reference in string context as a key — HASH(0x…), unique per container — and the post-increment means the first visit returns false and every later one returns true.

Note $seen must be passed down through the recursive calls. A fresh {} created inside each call would remember nothing.

Hand-built configuration and parsed tool output are almost never cyclic, so this is not something to add by default. It is what to reach for the moment a walker hangs or starts printing Deep recursion — which is nearly always a cycle rather than genuinely deep data.

6. When Not to Write a Walker

If you only want to look at a structure, do not write this.

use Data::Dumper;
print Dumper($design);

Chapter 7.12 covers it, including how to make the output stable and readable. A walker is the right tool when you need to do something per node — collect leaves, validate shapes, transform values, compute a summary. For inspection, Dumper is already written and already correct.

7. Why This Matters in Engineering Work

Tool output shapes drift. A script that assumes three levels breaks when a vendor adds a fourth. A walker that dispatches on what it finds does not, which is why validation and conversion utilities are usually written this way.

Path strings are the debugging payoff. When a 40,000-leaf structure has one wrong value, a dump that prints design{blocks}[7]{ports}[2] = undef tells you both the problem and the expression to inspect. That is worth far more than a pretty-printed tree you then have to count braces in.

And the interpolation trap is a real one. It is the kind of mistake that looks like a typo in the output rather than a bug in the code, and under strict it costs seconds instead of an afternoon — which is the clearest practical argument for the pragma in the whole module.

8. Common Mistakes

Interpolating a brace after a variable. "$path{$k}" is a hash element of %path. Concatenate instead.

Omitting the base case. The "" branch is what stops the recursion.

Omitting sort keys. The output order varies between runs and cannot be diffed.

Ignoring the else branch. A code reference or object is silently dropped, so you cannot tell what you actually have.

Pointing a naive walker at a cyclic structure. It will not terminate. Track visited references.

Reading Deep recursion as a size problem. It is usually a cycle.

Writing a walker just to look at the data. Use Data::Dumper.

9. Exercise

Exercise 1 — the walker. Build §1's four-key $design and run the walker. Confirm you get eight leaf lines and that the paths are valid Perl expressions by pasting one into a printf.

Exercise 2 — ragged input. Make matrix rows of lengths 2 and 1, add a key whose value is an empty array reference, and add a key whose value is undef. Run the same walker unchanged and report what each produces.

Exercise 3 — the tally. Run §3's visit and report the counts by kind. Then account for all four arrays and all eight scalars by name.

Exercise 4 — depth. Run depth on $design and report the number. Then nest one more level inside matrix and confirm it increases by one.

Exercise 5 — the trap, under strict. Change the recursive call to "$path{$_}" and record the exact compile error and exit status. Say which variable it named.

Exercise 6 — the trap, without strict. Run the same broken version with use strict removed and use warnings kept. Record STDOUT, STDERR and the exit status. Write one sentence on which of the two failures you would rather get.

Exercise 7 — the array form. Do the same for "$path[$_]" and record which variable the error names.

Exercise 8 — a cycle. Build my $n = { name => "a" }; $n->{self} = $n; and walk it. Record what happens, including any warning. Then add the $seen guard and confirm it terminates.

Exercise 9 — collect instead of print. Change the base case to push "$path = $node" onto an array rather than printing. Return the array and print its count. Then sort it and confirm the order matches Exercise 1.

10. Summary

• Any node is a hash reference, an array reference, or a plain value. ref() is the dispatch.
• The two container branches recurse; the plain-value branch is the base case. Without it the recursion never ends.
• Keep an else branch so code references, regexes and objects are reported rather than dropped.
• Extend the path with concatenation — $path . "{$k}". Interpolating "$path{$k}" is the hash element $path{$k} of %path, and under strict it will not compile.
• Without strict the same mistake prints an empty path and exits 0.
• sort keys in the hash branch makes the output reproducible and diffable.
• The walker needs no changes for ragged, uneven or mixed-depth data — that is the point of it.
• A cyclic structure will not terminate. Track visited references by their string form.
• Deep recursion at 100 levels is usually a cycle, not deep data.
• To merely look at a structure, use Data::Dumper rather than writing this.

Chapter 7.11 turns the dispatch idea into data: a hash whose values are subroutines, which replaces a long chain of elsif with a table you can add to at run time.