File Coverage

blib/lib/Struct/Path.pm

Criterion	Covered	Total	%
statement	206	206	100.0
branch	110	110	100.0
condition	35	35	100.0
subroutine	9	9	100.0
pod	4	4	100.0
total	364	364	100.0

package Struct::Path;

use 5.006;
use strict;
use warnings FATAL => 'all';
use parent 'Exporter';

use Carp 'croak';

our @EXPORT_OK = qw(
    implicit_step
    list_paths
    path
    path_delta
);

=head1 NAME

Struct::Path - Path for nested structures where path is also a structure

=begin html





=end html

=head1 VERSION

Version 0.83

=cut

our $VERSION = '0.83';

=head1 SYNOPSIS

    use Struct::Path qw(list_paths path);

    $s = [
        0,
        {
            two => {
                three => 3,
                four => 4
            }
        },
        undef
    ];

    @list = list_paths($s);                         # list paths and values
    # @list == (
    #   [[0]], \0,
    #   [[1],{K => ['two']},{K => ['four']}], \4,
    #   [[1],{K => ['two']},{K => ['three']}], \3,
    #   [[2]], \undef
    # )

    @r = path($s, [ [1],{K => ['two']} ]);         # get refs to values
    # @r == (\{four => 4,three => 3})

=head1 DESCRIPTION

Struct::Path provides functions to access/match/expand/list nested data
structures.

Why L are not enough? This module has no
conflicts for paths like '/a/0/c', where C<0> may be an array index or a key
for hash (depends on passed structure). This is vital in some cases, for
example, when one need to define exact path in structure, but unable to
validate it's schema or when structure itself doesn't yet exist (see
option C for L).

=head1 EXPORT

Nothing is exported by default.

=head1 ADDRESSING SCHEME

Path is a list of 'steps', each represents nested level in the structure.

Arrayref as a step stands for ARRAY and must contain desired items indexes or
be empty (means "all items"). Sequence for indexes define result sequence.

Hashref represent HASH and may contain key C or be empty. C's value
should be a list of desired keys and compiled regular expressions. Empty
hash or empty list for C means all keys, sequence in the list define
resulting sequence.

Coderef step is a hook - subroutine which may filter and/or modify
structure. Path as first argument and a stack (arrayref) of refs to traversed
substructures as second passed to it when executed, C<$_> set to current
substructure, C<$_{opts}> contains passed options. Some true (match) value or
false (doesn't match) value expected as output.

Sample:

    $path = [
        [1,7],                      # first spep
        {R => [qr/foo/,qr/bar/]}    # second step
        sub { exists $_->{bar} }    # third step
    ];

Struct::Path designed to be machine-friendly. See L
and L for human friendly path definition.

=head1 SUBROUTINES

=head2 implicit_step

    $bool = implicit_step($step);

Returns true value if step contains hooks or specified 'all' items or regexp
match.

=cut

sub implicit_step {
    if (ref $_[0] eq 'ARRAY') {
        return 1 unless (@{$_[0]});
    } elsif (ref $_[0] eq 'HASH') {
        return 1 if (exists $_[0]->{R} and @{$_[0]->{R}});
        return 1 unless (exists $_[0]->{K});
        return 1 unless (@{$_[0]->{K}});
        ref $_ eq 'Regexp' && return 1 for (@{$_[0]->{K}})
    } else { # hooks
        return 1;
    }

    return undef;
}

=head2 list_paths

Returns list of paths and references to their values from structure.

    @list = list_paths($structure, %opts)

=head3 Options

=over 4

=item depth C<<  >>

Don't dive into structure deeper than defined level.

=back

=cut

sub list_paths($;@) {
    my @stack = ([], \shift); # init: (path, ref)
    my %opts = @_;

    my (@out, $path, $ref);
    my $depth = defined $opts{depth} ? $opts{depth} : -1;

    while (($path, $ref) = splice @stack, 0, 2) {
        if (ref ${$ref} eq 'HASH' and @{$path} != $depth and keys %{${$ref}}) {
            map { unshift @stack, [@{$path}, {K => [$_]}], \${$ref}->{$_} }
                reverse sort keys %{${$ref}};
        } elsif (ref ${$ref} eq 'ARRAY' and @{$path} != $depth and @{${$ref}}) {
            map { unshift @stack, [@{$path}, [$_]], \${$ref}->[$_] }
                reverse 0 .. $#{${$ref}}
        } else {
            push @out, $path, $ref;
        }
    }

    return @out;
}

=head2 path

Returns list of references from structure.

    @found = path($structure, $path, %opts)

=head3 Options

=over 4

=item assign C<<  >>

Assign provided value to substructures pointed by path.

=item delete C<<  >>

Delete specified by path items from structure.

=item deref C<<  >>

Dereference result items.

=item expand C<<  >>

Expand structure if specified in path items doesn't exist. All newly created
items initialized by C.

=item paths C<<  >>

Return path for each result.

=item stack C<<  >>

Return stack of references to substructures.

=item strict C<<  >>

Croak if at least one element, specified by path, absent in the structure.

=back

All options are disabled (C) by default.

=cut

sub path($$;@) {
    my (undef, $path, %opts) = @_;

    croak "Arrayref expected for path" unless (ref $path eq 'ARRAY');
    croak "Unable to remove passed thing entirely (empty path passed)"
        if ($opts{delete} and not @{$path});

    my @level = ([], [\$_[0]]); # alias - to be able to rewrite passed scalar
    my $sc = 0; # step counter
    my ($items, @next, $steps, $refs, $step_type, @types);

    for my $step (@{$path}) {
        while (($steps, $refs) = splice @level, 0, 2) {
            croak "Reference expected for refs stack entry, step #$sc"
                unless (ref $refs->[-1]);

            if (($step_type = ref $step) eq 'ARRAY') {
                if (ref ${$refs->[-1]} ne 'ARRAY') {
                    croak "ARRAY expected on step #$sc, got " . ref ${$refs->[-1]}
                        if ($opts{strict});
                    next unless ($opts{expand});
                    ${$refs->[-1]} = [];
                }

                $items = @{$step} ? $step : [0 .. $#${$refs->[-1]}];
                for (@{$items}) {
                    unless (
                        $opts{expand} or
                        @{${$refs->[-1]}} > ($_ >= 0 ? $_ : abs($_ + 1))
                    ) {
                        croak "[$_] doesn't exist, step #$sc" if ($opts{strict});
                        next;
                    }

                    if ($_ < 0) {
                        if (@{${$refs->[-1]}} < abs($_)) {
                            # expand smoothly for out of range negative indexes
                            $_ = @{${$refs->[-1]}};
                        } else {
                            $_ += @{${$refs->[-1]}};
                        }
                    }

                    push @next, [@{$steps}, [$_]], [@{$refs}, \${$refs->[-1]}->[$_]];
                }

                if ($opts{delete} and $sc == $#{$path}) {
                    map { splice(@{${$refs->[-1]}}, $_, 1) if ($_ < @{${$refs->[-1]}}) }
                        reverse sort @{$items};
                }
            } elsif ($step_type eq 'HASH') {
                if (ref ${$refs->[-1]} ne 'HASH') {
                    croak "HASH expected on step #$sc, got " . ref ${$refs->[-1]}
                        if ($opts{strict});
                    next unless ($opts{expand});
                    ${$refs->[-1]} = {};
                }

                @types = grep { exists $step->{$_} } qw(K R);
                croak "Unsupported HASH definition, step #$sc" if (@types != keys %{$step});
                undef $items;

                for my $t (@types) {
                    unless (ref $step->{$t} eq 'ARRAY') {
                        my $type = $t eq 'K' ? "keys" : "regs";
                        croak "Unsupported HASH $type definition, step #$sc";
                    }

                    if ($t eq 'K') {
                        for my $i (@{$step->{K}}) {
                            if (ref $i eq 'Regexp') {
                                push @{$items}, grep { $_ =~ $i }
                                    keys %{${$refs->[-1]}};
                            } else {
                                unless ($opts{expand} or exists ${$refs->[-1]}->{$i}) {
                                    croak "{$i} doesn't exist, step #$sc" if $opts{strict};
                                    next;
                                }
                                push @{$items}, $i;
                            }
                        }
                    } else {
                        for my $g (@{$step->{R}}) {
                            push @{$items}, grep { $_ =~ $g } keys %{${$refs->[-1]}};
                        }
                    }
                }

                for (@types ? @{$items} : keys %{${$refs->[-1]}}) {
                    push @next, [@{$steps}, {K => [$_]}], [@{$refs}, \${$refs->[-1]}->{$_}];
                    delete ${$refs->[-1]}->{$_} if ($opts{delete} and $sc == $#{$path});
                }
            } elsif ($step_type eq 'CODE') {
                local $_ = ${$refs->[-1]};
                local $_{opts} = \%opts;
                $step->($steps, $refs) and push @next, $steps, $refs;
            } else {
                croak "Unsupported thing in the path, step #$sc";
            }
        }

        @level = splice @next;
        $sc++;
    }

    my @out;
    while (($path, $refs) = splice @level, 0, 2) {
        ${$refs->[-1]} = $opts{assign} if (exists $opts{assign});

        if ($opts{stack}) {
            map { $_ = ${$_} } @{$refs} if ($opts{deref});
        } else {
            $refs = $opts{deref} ? ${pop @{$refs}} : pop @{$refs};
        }

        push @out, ($opts{paths} ? ($path, $refs) : $refs);
    }

    return @out;
}

=head2 path_delta

Returns delta for two passed paths. By delta means list of steps from the
second path without beginning common steps for both.

    @delta = path_delta($path1, $path2)

=cut

sub path_delta($$) {
    my ($frst, $scnd) = @_;

    croak "Second path must be an arrayref" unless (ref $scnd eq 'ARRAY');
    return @{$scnd} unless (defined $frst);
    croak "First path may be undef or an arrayref" unless (ref $frst eq 'ARRAY');

    require B::Deparse;
    my $deparse = B::Deparse->new();
    my $i = 0;

    MAIN:
    while ($i < @{$frst} and ref $frst->[$i] eq ref $scnd->[$i]) {
        if (ref $frst->[$i] eq 'ARRAY') {
            last unless (@{$frst->[$i]} == @{$scnd->[$i]});
            for (0 .. $#{$frst->[$i]}) {
                last MAIN unless ($frst->[$i]->[$_] == $scnd->[$i]->[$_]);
            }
        } elsif (ref $frst->[$i] eq 'HASH') {
            last unless (@{$frst->[$i]->{K}} == @{$scnd->[$i]->{K}});
            for (0 .. $#{$frst->[$i]->{K}}) {
                last MAIN unless (
                    $frst->[$i]->{K}->[$_] eq
                    $scnd->[$i]->{K}->[$_]
                );
            }
        } elsif (ref $frst->[$i] eq 'CODE') {
            last unless (
                $deparse->coderef2text($frst->[$i]) eq
                $deparse->coderef2text($scnd->[$i])
            );
        } else {
            croak "Unsupported thing in the path, step #$i";
        }

        $i++;
    }

    return @{$scnd}[$i .. $#{$scnd}];
}

=head1 LIMITATIONS

Struct::Path will fail on structures with loops in references.

No object oriented interface provided.

=head1 AUTHOR

Michael Samoglyadov, C<<  >>

=head1 BUGS

Please report any bugs or feature requests to C,
or through the web interface at
L. I will be
notified, and then you'll automatically be notified of progress on your bug
as I make changes.

=head1 SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Struct::Path

You can also look for information at:

=over 4

=item * RT: CPAN's request tracker (report bugs here)

L

=item * AnnoCPAN: Annotated CPAN documentation

L

=item * CPAN Ratings

L

=item * Search CPAN

L

=back

=head1 SEE ALSO

L L L L L
L L L L L
L L L

L L L

=head1 LICENSE AND COPYRIGHT

Copyright 2016-2018 Michael Samoglyadov.

This program is free software; you can redistribute it and/or modify it
under the terms of either: the GNU General Public License as published
by the Free Software Foundation; or the Artistic License.

See L for more information.

=cut

1; # End of Struct::Path