File Coverage

blib/lib/Tree/XPathEngine.pm

Criterion	Covered	Total	%
statement	372	404	92.0
branch	121	170	71.1
condition	22	32	68.7
subroutine	49	50	98.0
pod	9	9	100.0
total	573	665	86.1

#$Id: /tree-xpathengine/trunk/lib/Tree/XPathEngine.pm 25 2006-02-15T15:34:11.453583Z mrodrigu  $
package Tree::XPathEngine;

use warnings;
use strict;

use vars qw($VERSION $AUTOLOAD $revision);

$VERSION = '0.05';
$Tree::XPathEngine::DEBUG = 0;

use vars qw/
        $WILD
        $NUMBER_RE
        $NODE_TYPE
        $AXIS_NAME
        %AXES
        $LITERAL
        $REGEXP_RE
        $REGEXP_MOD_RE
        %CACHE/;

use Tree::XPathEngine::Step;
use Tree::XPathEngine::Expr;
use Tree::XPathEngine::Function;
use Tree::XPathEngine::LocationPath;
use Tree::XPathEngine::Variable;
use Tree::XPathEngine::Literal;
use Tree::XPathEngine::Number;
use Tree::XPathEngine::NodeSet;
use Tree::XPathEngine::Root;

# Axis name to principal node type mapping
%AXES = (
        'ancestor' => 'element',
        'ancestor-or-self' => 'element',
        'attribute' => 'attribute',
        'child' => 'element',
        'descendant' => 'element',
        'descendant-or-self' => 'element',
        'following' => 'element',
        'following-sibling' => 'element',
        'parent' => 'element',
        'preceding' => 'element',
        'preceding-sibling' => 'element',
        'self' => 'element',
        );

$WILD          = qr{\*};
$NODE_TYPE     = qr{(?:(text|node)\(\))};
$AXIS_NAME     = '(?:' . join('|', keys %AXES) . ')::';
$NUMBER_RE     = qr{(?:\d+(?:\.\d*)?|\.\d+)};
$REGEXP_RE     = qr{(?:m?/(?:\\.|[^/])*/)};
$REGEXP_MOD_RE = qr{(?:[imsx]+)};
$LITERAL       = qr{(?:"[^"]*"|'[^']*')};

sub new {
    my $class = shift;
    my( %option)= @_;

    my $self = bless {}, $class;

    $self->{NAME}= $option{xpath_name_re} || qr/(?:[A-Za-z_][\w.-]*)/;
    $self->{NAME}= qr/(?:$self->{NAME})/; # add parens just to make sure we have them

    _debug("New Parser being created.\n") if( $Tree::XPathEngine::DEBUG);
    $self->{context_set} = Tree::XPathEngine::NodeSet->new();
    $self->{context_pos} = undef; # 1 based position in array context
    $self->{context_size} = 0; # total size of context
    $self->{vars} = {};
    $self->{direction} = 'forward';
    $self->{cache} = {};

    return $self;
}

sub find {
    my $self = shift;
    my( $path, $context) = @_;
    my $parsed_path= $self->_parse( $path);
    return $parsed_path->evaluate( $context);
}


sub matches {
    my $self = shift;
    my ($node, $path, $context) = @_;

    my @nodes = $self->findnodes( $path, $context);

    if (grep { "$node" eq "$_" } @nodes) { return 1; }
    return;
}

sub findnodes {
    my $self = shift;
    my ($path, $context) = @_;

    my $results = $self->find( $path, $context);

    if ($results->isa('Tree::XPathEngine::NodeSet'))
      { return $results->get_nodelist; }
    else
      { return ();   }
}


sub findnodes_as_string {
    my $self = shift;
    my ($path, $context) = @_;

    my $results = $self->find( $path, $context);

    if ($results->isa('Tree::XPathEngine::NodeSet')) {
        return join('', map { $_->to_string } $results->get_nodelist);
    }
    elsif ($results->isa('Tree::XPathEngine::Node')) {
        return $results->to_string;
    }
    else {
        return $results->value; # CHECK
    }
}

sub findvalue {
    my $self = shift;
    my ($path, $context) = @_;
    my $results = $self->find( $path, $context);
    return $results ? $results->xpath_to_literal : '';
}

sub exists
  { my $self = shift;
    my ($path, $context) = @_;
    my @nodeset = $self->findnodes( $path, $context);
    return scalar( @nodeset ) ? 1 : 0;
  }

sub get_var {
    my $self = shift;
    my $var = shift;
    $self->{vars}->{$var};
}

sub set_var {
    my $self = shift;
    my $var = shift;
    my $val = shift;
    $self->{vars}->{$var} = $val;
}

#sub _get_context_set  { $_[0]->{context_set}; }
sub _set_context_set  { $_[0]->{context_set} = $_[1]; }
sub _get_context_pos  { $_[0]->{context_pos}; }
sub _set_context_pos  { $_[0]->{context_pos} = $_[1]; }
sub _get_context_size { $_[0]->{context_set}->size; }
#sub _get_context_node { $_[0]->{context_set}->get_node($_[0]->{context_pos}); }

sub _parse {
    my $self = shift;
    my $path = shift;
    if ($CACHE{$path}) {
        return $CACHE{$path};
    }
    my $tokens = $self->_tokenize($path);

    $self->{_tokpos} = 0;
    my $tree = $self->_analyze($tokens);

    if ($self->{_tokpos} < scalar(@$tokens)) {
        # didn't manage to parse entire expression - throw an exception
        die "Parse of expression $path failed - junk after end of expression: $tokens->[$self->{_tokpos}]";
    }

    $CACHE{$path} = $tree;

    _debug("PARSED Expr to:\n", $tree->as_string, "\n") if( $Tree::XPathEngine::DEBUG);

    return $tree;
}

sub _tokenize {
    my $self = shift;
    my $path = shift;
    study $path;

    my @tokens;

    _debug("Parsing: $path\n") if( $Tree::XPathEngine::DEBUG);

    # Bug: We don't allow "'@' NodeType" which is in the grammar, but I think is just plain stupid.

    my $expected=''; # used to desambiguate conflicts (for REs)

    while( length($path))
      { my $token='';
        if( $expected eq 'RE' && ($path=~ m{\G\s*($REGEXP_RE $REGEXP_MOD_RE?)\s*}gcxs))
          { $token= $1; $expected=''; }
        elsif($path =~ m/\G
            \s* # ignore all whitespace
                ( # tokens
                $LITERAL|                           # literal string
                $NUMBER_RE|                         # digits
                \.\.|                               # parent
                \.|                                 # current
                ($AXIS_NAME)?$NODE_TYPE|            # node type test (probably useless in this context)
                \@($self->{NAME}|$WILD)|            # attribute
                \$$self->{NAME}|                    # variable reference
                ($AXIS_NAME)?($self->{NAME}|$WILD)| # NAME,NodeType,Axis::Test
                \!=|<=|\-|>=|\/\/|and|or|mod|div|   # multi-char seps
                =~|\!~|                             # regexp matching (not in the XPath spec)
                [,\+=\|<>\/\(\[\]\)]|               # single char seps
                (?
                (?
                $ # match end of query
            )
            \s* # ignore all whitespace
            /gcxs)
          {
            $token = $1;
            $expected= ($token=~ m{^[=!]~$}) ? 'RE' : '';
          }
        else
          { $token=''; last; }

        if (length($token))
          {
            _debug("TOKEN: $token\n") if( $Tree::XPathEngine::DEBUG);
            push @tokens, $token;
          }
      }

    if (pos($path) < length($path)) {
        my $marker = ("." x (pos($path)-1));
        $path = substr($path, 0, pos($path) + 8) . "...";
        $path =~ s/\n/ /g;
        $path =~ s/\t/ /g;
        die "Query:\n",
            "$path\n",
            $marker, "^^^\n",
            "Invalid query somewhere around here (I think)\n";
    }

    return \@tokens;
}

sub _analyze {
    my $self = shift;
    my $tokens = shift;
    # lexical analysis

    return _expr($self, $tokens);
}

sub _match {
    my ($self, $tokens, $match, $fatal) = @_;

    $self->{_curr_match} = '';
    return 0 unless $self->{_tokpos} < @$tokens;

    local $^W;

#    _debug ("match: $match\n") if( $Tree::XPathEngine::DEBUG);

    if ($tokens->[$self->{_tokpos}] =~ /^$match$/) {
        $self->{_curr_match} = $tokens->[$self->{_tokpos}];
        $self->{_tokpos}++;
        return 1;
    }
    else {
        if ($fatal) {
            die "Invalid token: ", $tokens->[$self->{_tokpos}], "\n";
        }
        else {
            return 0;
        }
    }
}

sub _expr {
    my ($self, $tokens) = @_;

    _debug( "in _exprexpr\n") if( $Tree::XPathEngine::DEBUG);

    return _or_expr($self, $tokens);
}

sub _or_expr {
    my ($self, $tokens) = @_;

    _debug( "in _or_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _and_expr($self, $tokens);
    while (_match($self, $tokens, 'or')) {
        my $or_expr = Tree::XPathEngine::Expr->new($self);
        $or_expr->set_lhs($expr);
        $or_expr->set_op('or');

        my $rhs = _and_expr($self, $tokens);

        $or_expr->set_rhs($rhs);
        $expr = $or_expr;
    }

    return $expr;
}

sub _and_expr {
    my ($self, $tokens) = @_;

    _debug( "in _and_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _match_expr($self, $tokens);
    while (_match($self, $tokens, 'and')) {
        my $and_expr = Tree::XPathEngine::Expr->new($self);
        $and_expr->set_lhs($expr);
        $and_expr->set_op('and');

        my $rhs = _match_expr($self, $tokens);

        $and_expr->set_rhs($rhs);
        $expr = $and_expr;
    }

    return $expr;
}

sub _match_expr {
    my ($self, $tokens) = @_;

    _debug( "in _match_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _equality_expr($self, $tokens);

    while (_match($self, $tokens, '[=!]~')) {
        my $match_expr = Tree::XPathEngine::Expr->new($self);
        $match_expr->set_lhs($expr);
        $match_expr->set_op($self->{_curr_match});

        my $rhs = _equality_expr($self, $tokens);

        $match_expr->set_rhs($rhs);
        $expr = $match_expr;
    }

    return $expr;
}

sub _equality_expr {
    my ($self, $tokens) = @_;

    _debug( "in _equality_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _relational_expr($self, $tokens);
    while (_match($self, $tokens, '!?=')) {
        my $eq_expr = Tree::XPathEngine::Expr->new($self);
        $eq_expr->set_lhs($expr);
        $eq_expr->set_op($self->{_curr_match});

        my $rhs = _relational_expr($self, $tokens);

        $eq_expr->set_rhs($rhs);
        $expr = $eq_expr;
    }

    return $expr;
}

sub _relational_expr {
    my ($self, $tokens) = @_;

    _debug( "in _relational_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _additive_expr($self, $tokens);
    while (_match($self, $tokens, '(<|>|<=|>=)')) {
        my $rel_expr = Tree::XPathEngine::Expr->new($self);
        $rel_expr->set_lhs($expr);
        $rel_expr->set_op($self->{_curr_match});

        my $rhs = _additive_expr($self, $tokens);

        $rel_expr->set_rhs($rhs);
        $expr = $rel_expr;
    }

    return $expr;
}

sub _additive_expr {
    my ($self, $tokens) = @_;

    _debug( "in _additive_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _multiplicative_expr($self, $tokens);
    while (_match($self, $tokens, '[\\+\\-]')) {
        my $add_expr = Tree::XPathEngine::Expr->new($self);
        $add_expr->set_lhs($expr);
        $add_expr->set_op($self->{_curr_match});

        my $rhs = _multiplicative_expr($self, $tokens);

        $add_expr->set_rhs($rhs);
        $expr = $add_expr;
    }

    return $expr;
}

sub _multiplicative_expr {
    my ($self, $tokens) = @_;

    _debug( "in _multiplicative_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _unary_expr($self, $tokens);
    while (_match($self, $tokens, '(\\*|div|mod)')) {
        my $mult_expr = Tree::XPathEngine::Expr->new($self);
        $mult_expr->set_lhs($expr);
        $mult_expr->set_op($self->{_curr_match});

        my $rhs = _unary_expr($self, $tokens);

        $mult_expr->set_rhs($rhs);
        $expr = $mult_expr;
    }

    return $expr;
}

sub _unary_expr {
    my ($self, $tokens) = @_;

    _debug( "in _unary_expr\n") if( $Tree::XPathEngine::DEBUG);

    if (_match($self, $tokens, '-')) {
        my $expr = Tree::XPathEngine::Expr->new($self);
        $expr->set_lhs(Tree::XPathEngine::Number->new(0));
        $expr->set_op('-');
        $expr->set_rhs(_unary_expr($self, $tokens));
        return $expr;
    }
    else {
        return _union_expr($self, $tokens);
    }
}

sub _union_expr {
    my ($self, $tokens) = @_;

    _debug( "in _union_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _path_expr($self, $tokens);
    while (_match($self, $tokens, '\\|')) {
        my $un_expr = Tree::XPathEngine::Expr->new($self);
        $un_expr->set_lhs($expr);
        $un_expr->set_op('|');

        my $rhs = _path_expr($self, $tokens);

        $un_expr->set_rhs($rhs);
        $expr = $un_expr;
    }

    return $expr;
}

sub _path_expr {
    my ($self, $tokens) = @_;

    _debug( "in _path_expr\n") if( $Tree::XPathEngine::DEBUG);

    # _path_expr is _location_path | _filter_expr | _filter_expr '//?' _relative_location_path

    # Since we are being predictive we need to find out which function to call next, then.

    # LocationPath either starts with "/", "//", ".", ".." or a proper Step.

    my $expr = Tree::XPathEngine::Expr->new($self);

    my $test = $tokens->[$self->{_tokpos}];

    # Test for AbsoluteLocationPath and AbbreviatedRelativeLocationPath
    if ($test =~ /^(\/\/?|\.\.?)$/) {
        # LocationPath
        $expr->set_lhs(_location_path($self, $tokens));
    }
    # Test for AxisName::...
    elsif (_is_step($self, $tokens)) {
        $expr->set_lhs(_location_path($self, $tokens));
    }
    else {
        # Not a LocationPath
        # Use _filter_expr instead:

        $expr = _filter_expr($self, $tokens);
        if (_match($self, $tokens, '//?')) {
            my $loc_path = Tree::XPathEngine::LocationPath->new();
            push @$loc_path, $expr;
            if ($self->{_curr_match} eq '//') {
                push @$loc_path, Tree::XPathEngine::Step->new($self, 'descendant-or-self',
                                        Tree::XPathEngine::Step::test_nt_node() );
            }
            push @$loc_path, _relative_location_path($self, $tokens);
            my $new_expr = Tree::XPathEngine::Expr->new($self);
            $new_expr->set_lhs($loc_path);
            return $new_expr;
        }
    }

    return $expr;
}

sub _filter_expr {
    my ($self, $tokens) = @_;

    _debug( "in _filter_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = _primary_expr($self, $tokens);
    while (_match($self, $tokens, '\\[')) {
        # really PredicateExpr...
        $expr->push_predicate(_expr($self, $tokens));
        _match($self, $tokens, '\\]', 1);
    }

    return $expr;
}

sub _primary_expr {
    my ($self, $tokens) = @_;

    _debug( "in _primary_expr\n") if( $Tree::XPathEngine::DEBUG);

    my $expr = Tree::XPathEngine::Expr->new($self);

    if (_match($self, $tokens, $LITERAL)) {
        # new Literal with $self->{_curr_match}...
        $self->{_curr_match} =~ m/^(["'])(.*)\1$/;
        $expr->set_lhs(Tree::XPathEngine::Literal->new($2));
    }
    elsif (_match($self, $tokens, "$REGEXP_RE$REGEXP_MOD_RE?")) {
        # new Literal with $self->{_curr_match} turned into a regexp...
        my( $regexp, $mod)= $self->{_curr_match} =~  m{($REGEXP_RE)($REGEXP_MOD_RE?)};
        $regexp=~ s{^m?s*/}{};
        $regexp=~ s{/$}{};
        if( $mod) { $regexp=~ "(?$mod:$regexp)"; } # move the mods inside the regexp
        $expr->set_lhs(Tree::XPathEngine::Literal->new($regexp));
    }
    elsif (_match($self, $tokens, $NUMBER_RE)) {
        # new Number with $self->{_curr_match}...
        $expr->set_lhs(Tree::XPathEngine::Number->new($self->{_curr_match}));
    }
    elsif (_match($self, $tokens, '\\(')) {
        $expr->set_lhs(_expr($self, $tokens));
        _match($self, $tokens, '\\)', 1);
    }
    elsif (_match($self, $tokens, "\\\$$self->{NAME}")) {
        # new Variable with $self->{_curr_match}...
        $self->{_curr_match} =~ /^\$(.*)$/;
        $expr->set_lhs(Tree::XPathEngine::Variable->new($self, $1));
    }
    elsif (_match($self, $tokens, $self->{NAME})) {
        # check match not Node_Type - done in lexer...
        # new Function
        my $func_name = $self->{_curr_match};
        _match($self, $tokens, '\\(', 1);
        $expr->set_lhs(
                Tree::XPathEngine::Function->new(
                    $self,
                    $func_name,
                    _arguments($self, $tokens)
                )
            );
        _match($self, $tokens, '\\)', 1);
    }
    else {
        die "Not a _primary_expr at ", $tokens->[$self->{_tokpos}], "\n";
    }

    return $expr;
}

sub _arguments {
    my ($self, $tokens) = @_;

    _debug( "in _arguments\n") if( $Tree::XPathEngine::DEBUG);

    my @args;

    if($tokens->[$self->{_tokpos}] eq ')') {
        return \@args;
    }

    push @args, _expr($self, $tokens);
    while (_match($self, $tokens, ',')) {
        push @args, _expr($self, $tokens);
    }

    return \@args;
}

sub _location_path {
    my ($self, $tokens) = @_;

    _debug( "in _location_path\n") if( $Tree::XPathEngine::DEBUG);

    my $loc_path = Tree::XPathEngine::LocationPath->new();

    if (_match($self, $tokens, '/')) {
        # root
        _debug("h: Matched root\n") if( $Tree::XPathEngine::DEBUG);
        push @$loc_path, Tree::XPathEngine::Root->new();
        if (_is_step($self, $tokens)) {
            _debug("Next is step\n") if( $Tree::XPathEngine::DEBUG);
            push @$loc_path, _relative_location_path($self, $tokens);
        }
    }
    elsif (_match($self, $tokens, '//')) {
        # root
        push @$loc_path, Tree::XPathEngine::Root->new();
        my $optimised = _optimise_descendant_or_self($self, $tokens);
        if (!$optimised) {
            push @$loc_path, Tree::XPathEngine::Step->new($self, 'descendant-or-self',
                                Tree::XPathEngine::Step::test_nt_node);
            push @$loc_path, _relative_location_path($self, $tokens);
        }
        else {
            push @$loc_path, $optimised, _relative_location_path($self, $tokens);
        }
    }
    else {
        push @$loc_path, _relative_location_path($self, $tokens);
    }

    return $loc_path;
}

sub _optimise_descendant_or_self {
    my ($self, $tokens) = @_;

    _debug( "in _optimise_descendant_or_self\n") if( $Tree::XPathEngine::DEBUG);

    my $tokpos = $self->{_tokpos};

    # // must be followed by a Step.
    if ($tokens->[$tokpos+1] && $tokens->[$tokpos+1] eq '[') {
        # next token is a predicate
        return;
    }
    elsif ($tokens->[$tokpos] =~ /^\.\.?$/) {
        # abbreviatedStep - can't optimise.
        return;
    }
    else {
        _debug("Trying to optimise //\n") if( $Tree::XPathEngine::DEBUG);
        my $step = _step($self, $tokens);
        if ($step->{axis} ne 'child') {
            # can't optimise axes other than child for now...
            $self->{_tokpos} = $tokpos;
            return;
        }
        $step->{axis} = 'descendant';
        $step->{axis_method} = 'axis_descendant';
        $self->{_tokpos}--;
        $tokens->[$self->{_tokpos}] = '.';
        return $step;
    }
}

sub _relative_location_path {
    my ($self, $tokens) = @_;

    _debug( "in _relative_location_path\n") if( $Tree::XPathEngine::DEBUG);

    my @steps;

    push @steps,_step($self, $tokens);
    while (_match($self, $tokens, '//?')) {
        if ($self->{_curr_match} eq '//') {
            my $optimised = _optimise_descendant_or_self($self, $tokens);
            if (!$optimised) {
                push @steps, Tree::XPathEngine::Step->new($self, 'descendant-or-self',
                                        Tree::XPathEngine::Step::test_nt_node);
            }
            else {
                push @steps, $optimised;
            }
        }
        push @steps, _step($self, $tokens);
        if (@steps > 1 &&
                $steps[-1]->{axis} eq 'self' &&
                $steps[-1]->{test} == Tree::XPathEngine::Step::test_nt_node) {
            pop @steps;
        }
    }

    return @steps;
}

sub _step {
    my ($self, $tokens) = @_;

    _debug( "in _step\n") if( $Tree::XPathEngine::DEBUG);

    if (_match($self, $tokens, '\\.')) {
        # self::node()
        return Tree::XPathEngine::Step->new($self, 'self', Tree::XPathEngine::Step::test_nt_node);
    }
    elsif (_match($self, $tokens, '\\.\\.')) {
        # parent::node()
        return Tree::XPathEngine::Step->new($self, 'parent', Tree::XPathEngine::Step::test_nt_node);
    }
    else {
        # AxisSpecifier NodeTest Predicate(s?)
        my $token = $tokens->[$self->{_tokpos}];

        _debug("p: Checking $token\n") if( $Tree::XPathEngine::DEBUG);

        my $step;
        if ($token =~ /^\@($self->{NAME}|$WILD)$/) {
            $self->{_tokpos}++;
                        if ($token eq '@*') {
                            $step = Tree::XPathEngine::Step->new($self,
                                    'attribute',
                                    Tree::XPathEngine::Step::test_attr_any,
                                    '*');
                        }
                        elsif ($token =~ /^\@($self->{NAME})$/) {
                            $step = Tree::XPathEngine::Step->new($self,
                                    'attribute',
                                    Tree::XPathEngine::Step::test_attr_name,
                                    $1);
                        }
        }
        elsif ($token =~ /^$WILD$/) { # *
            $self->{_tokpos}++;
            $step = Tree::XPathEngine::Step->new($self, 'child',
                                Tree::XPathEngine::Step::test_any,
                                $token);
        }
        elsif ($token =~ /^$self->{NAME}$/) { # name:name
            $self->{_tokpos}++;
            $step = Tree::XPathEngine::Step->new($self, 'child',
                                Tree::XPathEngine::Step::test_name,
                                $token);
        }
        elsif ($token eq 'text()') {
            $self->{_tokpos}++;
            $step = Tree::XPathEngine::Step->new($self, 'child',
                    Tree::XPathEngine::Step::test_nt_text);
        }
        elsif ($token eq 'node()') {
            $self->{_tokpos}++;
            $step = Tree::XPathEngine::Step->new($self, 'child',
                    Tree::XPathEngine::Step::test_nt_node);
        }
        elsif ($token =~ /^($AXIS_NAME)($self->{NAME}|$WILD|$NODE_TYPE)$/) {
                    my $axis = substr( $1, 0, -2);
                    $self->{_tokpos}++;
                    $token = $2;
            if ($token =~ /^$WILD$/) { # *
                $step = Tree::XPathEngine::Step->new($self, $axis,
                                    (($axis eq 'attribute') ?
                                    Tree::XPathEngine::Step::test_attr_any
                                        :
                                    Tree::XPathEngine::Step::test_any),
                                    $token);
            }
            elsif ($token =~ /^$self->{NAME}$/) { # name:name
                $step = Tree::XPathEngine::Step->new($self, $axis,
                                    (($axis eq 'attribute') ?
                                    Tree::XPathEngine::Step::test_attr_name
                                        :
                                    Tree::XPathEngine::Step::test_name),
                                    $token);
            }
            elsif ($token eq 'text()') {
                $step = Tree::XPathEngine::Step->new($self, $axis,
                        Tree::XPathEngine::Step::test_nt_text);
            }
            elsif ($token eq 'node()') {
                $step = Tree::XPathEngine::Step->new($self, $axis,
                        Tree::XPathEngine::Step::test_nt_node);
            }
            else {
                die "Shouldn't get here";
            }
        }
        else {
            die "token $token doesn't match format of a 'Step'\n";
        }

        while (_match($self, $tokens, '\\[')) {
            push @{$step->{predicates}}, _expr($self, $tokens);
            _match($self, $tokens, '\\]', 1);
        }

        return $step;
    }
}

sub _is_step {
    my ($self, $tokens) = @_;

    my $token = $tokens->[$self->{_tokpos}];

    return unless defined $token;

    _debug("p: Checking if '$token' is a step\n") if( $Tree::XPathEngine::DEBUG);

    local $^W=0;

    if(   ($token eq 'processing-instruction')
       || ($token =~ /^\@($self->{NAME}|$WILD)$/)
       || (    ($token =~ /^($self->{NAME}|$WILD)$/ )
            && ( ($tokens->[$self->{_tokpos}+1] || '') ne '(') )
       || ($token =~ /^$NODE_TYPE$/)
       || ($token =~ /^$AXIS_NAME($self->{NAME}|$WILD|$NODE_TYPE)$/)
      )
      { return 1; }
    else
      { _debug("p: '$token' not a step\n") if( $Tree::XPathEngine::DEBUG);
        return;
      }
}

sub _debug {

    my ($pkg, $file, $line, $sub) = caller(1);

    $sub =~ s/^$pkg\:://;

    while (@_) {
        my $x = shift;
        $x =~ s/\bPKG\b/$pkg/g;
        $x =~ s/\bLINE\b/$line/g;
        $x =~ s/\bg\b/$sub/g;
        print STDERR $x;
    }
}


__END__