TPath - general purpose path languages for trees
version 1.007
# we define our trees package MyTree; use overload '""' => sub { my $self = shift; my $tag = $self->{tag}; my @children = @{ $self->{children} }; return "<$tag/>" unless @children; local $" = ''; "<$tag>@children</$tag>"; }; sub new { my ( $class, %opts ) = @_; die 'tag required' unless $opts{tag}; bless { tag => $opts{tag}, children => $opts{children} // [] }, $class; } sub add { my ( $self, @children ) = @_; push @{ $self->{children} }, @children; } # teach TPath::Forester how to get the information it needs package MyForester; use Moose; use MooseX::MethodAttributes; # needed for @tag attribute below with 'TPath::Forester'; # implement required methods sub children { my ( $self, $n ) = @_; @{ $n->{children} }; } sub tag { my ( $self, $n ) = @_; $n->{tag}; } sub tag_at : Attr(tag) { # tags receive the selection context, not the bare node my ( $self, $context ) = @_; $context->n->{tag}; } package main; # make the tree # a # /|\ # / | \ # b c \ # /\ | d # e f | /|\ # h / | \ # /| i j \ # l | | |\ \ # m n o p \ # /| /|\ \ # s t u v w k # / \ # q r # / \ # x y # | # z my %nodes = map { $_ => MyTree->new( tag => $_ ) } 'a' .. 'z'; $nodes{a}->add( @nodes{qw(b c d)} ); $nodes{b}->add( @nodes{qw(e f)} ); $nodes{c}->add( $nodes{h} ); $nodes{d}->add( @nodes{qw(i j k)} ); $nodes{h}->add( @nodes{qw(l m)} ); $nodes{i}->add( $nodes{n} ); $nodes{j}->add( @nodes{qw(o p)} ); $nodes{k}->add( @nodes{qw(q r)} ); $nodes{m}->add( @nodes{qw(s t)} ); $nodes{p}->add( @nodes{qw(u v w)} ); $nodes{r}->add( @nodes{qw(x y)} ); $nodes{y}->add( $nodes{z} ); my $root = $nodes{a}; # make our forester my $rhood = MyForester->new; # index our tree (not necessary, but efficient) my $index = $rhood->index($root); # try out some paths my @nodes = $rhood->path('//r')->select( $root, $index ); print scalar @nodes, "\n"; # 1 print $nodes[0], "\n"; # <r><x/><y><z/></y></r> print $_ for $rhood->path('leaf::*[@tag > "o"]')->select( $root, $index ) ; # <s/><t/><u/><v/><w/><q/><x/><z/> print "\n"; print $_->{tag} for $rhood->path('//*[@tsize = 3]')->select( $root, $index ); # bm print "\n"; @nodes = $rhood->path('/>~[bh-z]~')->select( $root, $index ); print $_->{tag} for @nodes; # bhijk print "\n"; # we can map nodes back to their parents @nodes = $rhood->path('//*[parent::~[adr]~]')->select( $root, $index ); print $_->{tag} for @nodes; # bcdijkxy print "\n";
TPath provides an xpath-like language for arbitrary trees. You implement a minimum of two methods -- children and tag -- and then you can explore your trees via concise, declarative paths.
children
tag
In tpath, "attributes" are node attributes of any sort and are implemented as methods that return these attributes, or undef if the attribute is undefined for the node.
undef
The object in which the two required methods are implemented is a "forester" (TPath::Forester), something that understands your trees. In general, to use tpath you instantiate a forester and then call the forester's methods.
Forester objects make use of an index (TPath::Index), which caches information not present in, or not cheaply extracted from, the nodes themselves. If no index is explicitly provided it is created, but one can gain some efficiency by reusing an index when selecting paths from a tree. And one can use a forester's index method to produce a TPath::Index.
index
TPath::Index
The paths themselves are compiled into reusable TPath::Expression objects that can be applied to multiple trees. One use's a forester's path method to produce a TPath::Expression.
path
TPath::Expression
TPath works by representing an expression as a pipeline of selectors and filters. Each pair of a selector and some set of filters is called a "step". At each step one has a set of context nodes. One applies the selectors to each context node, returning a candidate node set, and then one passes these candidates through the filtering predicates. The remainder becomes the context node set for the next step. If this is the last step, the surviving candidates are the nodes selected by the expression. A node will only occur once among those returned and the order of their return will be the order of their discovery. Search is depth-first pre-ordered -- parents returned before children.
The tpath algorithm presupposes the tree it is used against is static, at least for the life of the index it is using. If the tree is mutating, you must at least ensure that it does not mutate during the functional life of any index. The consequence of not doing so may be inaccurate queries.
A tpath expression has one or more sub-paths.
//a/b | preceding::d/*
Sub-paths are separated by the pipe symbol | and optional space.
|
The nodes selected by a path is the union of the nodes selected by each sub-path in the order of their discovery. The search is left-to-right and depth first. If a node and its descendants are both selected, the node will be listed first.
//a/b[0]/>c[@d]
Each step consists of a separator (optional on the first step), a tag selector, and optionally some number of predicates.
a/b/c/>d
/a/b//c/>d
//a/b//c/>d
/>a/b//c/>d
The null separator is simply the absence of a separator and can only occur before the first step. It means "relative to the context node". Thus is it essentially the same as the file path formalism, where /a means the file a in the root directory and a means the file a in the current directory.
/a
a
Note, here and in the following discussion we speak of a "root" node, but in reality the node in question is not the tree root but the node to which the expression is applied. This may be a bit confusing, but it simplifies the interpretation of expressions. If you genuinely want to begin at the root node, use the :root selector, described below. Since in general one will apply an expression to a tree's root node, in general this confusion of terminology is harmless. But know that if you pick a node at random from a tree and apply an expression to it, this will become the "root" as far as the various separator definitions here and below are concerned.
:root
The single slash separator means "search among the context node's children", or if it precedes the first step it means that the context node is the root node.
The double slash separator means "search among the descendants of the context node" or, if the context node is the root, "search among the root node and its descendants".
The /> separator means "search among the descendants of the context node (or the context node and its descendants if the context node is root), but omit from consideration any node dominated by a node matching the selector". Written out like this this may be confusing, but it is a surprisingly useful separator. Consider the following tree
/>
a / \ b a | | \ a b a | | b b
The expression />b when applied to the root node will select all the b nodes except the leftmost leaf b, which is screened from the root by its grandparent b node. That is, going down any path from the context node />b will match the first node it finds matching the selector -- the matching node closest to the context node.
/>b
b
Selectors select a candidate set for later filtering by predicates.
A literal selector selects the nodes whose tag matches, in a tree-appropriate sense of "match", a literal expression.
Any string may be used to represent a literal selector, but certain characters may have to be escaped with a backslash. The expectation is that the literal will begin with a word character, _, or $ and any subsequent character is either one of these characters, a number character or a hyphen or colon followed by one of these or a number character. The escape character, as usual, is a backslash. Any unexpected character must be escaped. So
$
a\\b
represents the literal a\b.
a\b
There is also a quoting convention that one can use to avoid many escapes inside a tag name.
/:"a tag name you otherwise would have to put a lot of escapes in"
See the Grammar section below for details.
~a~
A regex selector selects the nodes whose tag matches a regular expression delimited by tildes. Within the regular expression a tilde must be escaped, of course. A tilde within a regular expression is represented as a pair of tildes. The backslash, on the other hand, behaves as it normally does within a regular expression.
Any attribute may be used as a selector so long as it is preceded by something other than the null separator -- in other words, @ cannot be the first character in a path. This is because attributes may take arguments and among other things these arguments can be both expressions and other attributes. If @foo were a legitimate path expression it would be ambiguous how to compile @bar(@foo). Is the argument an attribute or a path with an attribute selector? You can produce the effect of an attribute selector with the null separator, however, in two ways
@
@foo
@bar(@foo)
child::@foo
./@foo
the second of these will be normalized in parsing to precisely what one would expect with a @foo path.
The attribute naming conventions are the same as those of tags with the exception that attributes are always preceded by @.
The ^ character before a literal, regex, or attribute selector will convert it into a complement selector.
^
//^foo
//^~foo~
//^@foo
Complement selectors select nodes not selected by the unmodified selector: //^foo will select any node without the foo tag, //~a~, any node whose tag does not contain the a character, and so forth.
foo
//~a~
The wildcard selector selects all the nodes on the relevant axis. The default axis is child, so //b/* will select all the children of b nodes.
child
//b/*
If you construct a forester with the case_insensitive parameter set to true
case_insensitive
my $f = MyForester->new( case_insensitive => 1 );
the tag selectors in all expressions compiled by this forester will be case insensitive. So then //INPUT will match INPUT and input and InPuT and so forth. The same is true for //input and //~input~ and //^INPUT etc. If your Perl version is 5.16 or higher, the native fc function will be used for case normalization. Otherwise, if Unicode::CaseFolding is available, its fc function will be used. If no fc function is available, lc will be used for case folding.
//INPUT
INPUT
input
InPuT
//input
//~input~
//^INPUT
fc
lc
To illustrate the nodes on various axes I will using the following tree, showing which nodes are selected from the tree relative the the d node. Selected nodes will be in capital letters.
d
root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/adjacent::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b C d E f /|\ /|\ /|\ g h i j k l m n o | | | p q r
The adjacent axis might be called the adjacent-sibling axis. It selects the nearest siblings of the context node passing the test. //foo/adjacent::p will select the immediately preceding and following p siblings of foo nodes.
adjacent
adjacent-sibling
//foo/adjacent::p
p
//d/ancestor::* ROOT | __A__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/ancestor-or-self::* ROOT | __A__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c D e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/child::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i J K L m n o | | | p q r
//d/descendant::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i J K L m n o | | | p Q r
//d/descendant-or-self::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c D e f /|\ /|\ /|\ g h i J K L m n o | | | p Q r
//d/following::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d E F /|\ /|\ /|\ g h i j k l M N O | | | p q R
//d/following-sibling::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d E F /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/leaf::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i J k L m n o | | | p Q r
//d/parent::* root | __A__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/preceding::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ B C d e f /|\ /|\ /|\ G H I j k l m n o | | | P q r
//d/preceding-sibling::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ B C d e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/previous::* ROOT | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c d e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
The previous axis is a bit different from the others. It doesn't concern the structure of the tree but the history of node selection. The root node is always included because it is always the initial selection context.
By itself the previous axis is not terribly useful, as it is silly in general to select a node, then other nodes, then backtrack. It is useful, however, when one wants to compare properties of different nodes in the selection history. See also the :p selector, which selects the immediately preceding node in the selection history.
:p
//d/self::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ b c D e f /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/sibling::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ B C d E F /|\ /|\ /|\ g h i j k l m n o | | | p q r
//d/sibling-or-self::* root | __a__ / /|\ \ / / | \ \ / / | \ \ / / | \ \ / / | \ \ B C D E F /|\ /|\ /|\ g h i j k l m n o | | | p q r
//a/b[0]/>c[@d][@e < 'string'][@f or @g]
Predicates are the sub-expressions in square brackets after selectors. They represents tests that filter the candidate nodes selected by the selectors.
//foo/bar[0]
An index predicate simply selects the indexed item out of a list of candidates. By default, the first index is 0, unlike in XML, so the expression above selects the first bar under every foo. This is configurable during the construction of your forester, however. If you pass in the one_based property
one_based
my $f = MyForester->new( one_based => 1 );
The forester will use one-based indexing, so its index predicates will work identically to index predicates in xpath. (This also affects the @index and @pick attributes. See below.)
@index
@pick
The index rules are the same as those for Perl arrays: 0 is the first item; negative indices count from the end, so -1 retrieves the last item. Negative indices behave the same regardless of whether the one_based property has been set to true.
In general, an index indicates the location of a node among its siblings which have survived and preceding filters. For example
//*[0]
picks all nodes that are the first child of their parent (also the root, which has no parent). This is distinct from /descendant-or-self::*[0], which will simply pick the root.
/descendant-or-self::*[0]
//a[0]
picks all nodes that are the first child of an a node. This is distinct from /descendant-or-self::a[0], where the only node returned will simply be the first node picked on this axis.
/descendant-or-self::a[0]
//a[@foo][0]
picks all nodes that are the first child of an a node having the property @foo. This is distinct from /descendant-or-self::a[@foo][0], which will pick only the first a node with the @foo property.
/descendant-or-self::a[@foo][0]
These predicates are all "inner" predicates. It is also possible to specify "outer" predicates, like so
(//*)[0] (//a)[0] (//a[@foo])[0]
In this case, the index is for the collection of all nodes selected up to this point, not relative to a node's similar siblings. So the first expression picks the first node which is the first child of its parent; the second picks the first node anywhere that is the first child of an a node; the third picks the first node anywhere that is the first @foo child node of an a node.
Any predicate may be either inner or outer, but the distinction is most relevant to index predicates for steps with the // separator.
//
a[b]
A path predicate is true if the node set it selects starting at the context node is not empty. Given the tree
a / \ b a | | a b
the path //a[b] would select only the two non-leaf a nodes.
//a[b]
a[@leaf]
An attribute predicate is true if its context node bears the given attribute. (For the definition of attributes, see below.) Given the tree
the path //a[@leaf] would select only the leaf a node.
//a[@leaf]
Attribute tests are predicaters which compare two values. The values may be attributes, expressions, other attribute tests, or literals, either strings or numbers.
//a[@b = 1] # simple equality test //a[* % 2 == 0] # mathematical expressions //a[@foo > :pi] # comparison to a named constant //a[@foo > "pi"] # alphabetical sort order comparison
The name "attribute test" is actually a misnomer: originally one of the two items compared had to be an attribute. Now any two values from the list above are acceptable. If both values are constant, the test is evaluated during compilation. Analytically true tests are discarded and analytically false ones cause an error to be thrown.
//a[ (@foo + 1) ** 2 > @bar ] //a[ :sqrt(@foo) == 1.414 ]
Basic mathematical expressions are acceptable in attribute tests. The standard precedence relations among operators are preserved, the operators all have the same representation as in Perl, and one may group expressions with parentheses to make precedence explicit.
There are two named constants, :pi and :e, the circle constant and the base of the natural logarithm. These are preceded by colons to distinguish them from path expressions. The operators -- +, -, *, /, %, and ** -- all may also be preceded by a colon when necessary to distinguish them from repetition characters or the wildcard character. This will rarely be necessary, but consider
:pi
:e
+
-
*
/
%
**
//* [ a * /b = 3 ]
Without the colon, this is taken to be an assertion about the cardinality of the set of nodes selected by the expression a*/b. If one wants this to be interpreted as concerning the product of the cardinalities of two sets of nodes, one should write it as
a*/b
//* [ a :* /b = 3 ]
The colon also must precede the various unary mathematical expression tpath understands:
:abs :acos :asin :atan :ceil :cos :exp :floor :int :log :log10 :sin :sqrt :tan
These are all either the functions provided by Perl itself or those provided by the POSIX module.
a[@b = 1] a[@b = "c"] a[@b = @c] a[@b == @c] a[@b != @c] ...
The equality and inequality attribute tests, as you would expect, determine whether the left argument is equal to the right by some definition of equality. If one operator is a number and the other a collection, it's equality of cardinality. If one is a string, it is whether their printed forms are identical. If they are both objects or collections, either referential or semantic identity is measured. Referential identity means the collections or objects must be the same individual -- must be stored at the same memory address. This is the meaning of the double equals sign. The single equals sign designates semantic identity, meaning, in the case of collections, that they are deeply equal -- the same values stored under the same indices or keys. If one of the items compared is an object and it has an equals method, this method is invoked as a semantic equality test (this is the Java convention). Otherwise, referential identity (==, which may be overloaded) is required. Objects are not treated as containers. Finally, if an object is compared to a string, it will be the stringification of the former that is compared to the latter using the c<eq> operator when semantic identity is required.
equals
==
The != comparator behaves as you would expect so long as one or the other of the two operands is either a string or a number. That is, it is the negation of = or ==. Otherwise, collections are converted to cardinalities and objects to strings, with string comparison being used if either argument is an object. If you wish the negation of = or == with collections or objects, you must negate the positive form:
!=
=
a[!(@b = @c)] a[!(@b == @c)]
a[@b < 1] a[@b < "c"] a[@b < @c] a[@b > 1] a[@b <= 1] ...
The ranking operators require some partial order of the operands. If both evaluate to numbers or strings, the respective orders of these are used. If one is a string, string sort order dominates. If both are collections, numeric sorting by cardinality is used. Objects are sorted by string comparison.
The matching operators look for character patterns within strings. They fall into two groups: the regex matchers and the index matchers.
a[@b =~ '(?<!c)d'] # regex matching a[@b !~ '(?<!c)d'] a[@b =~ /(?<!c)d/] a[@b =~ :m{(?<!/)d}] a[@b =~ :m/ (?<!c) d /imsx] a[@b =~ @c] ... a[@b |= 'c'] # index matching a[@b =|= 'c'] a[@b =| 'c'] a[@b |= @c] ...
regex matching
The two regex matching operators, =~ and !~, function as you would expect: the right operand is stringified and compiled into a regular expression and matched against the left operand. If the left operand is constant -- a string or a number -- this regex compilation occurs at compile time. Otherwise, it must be performed for every match, at some cost to efficiency.
=~
!~
Note that there are special quoting conventions for the right argument of the regex operator. You may use simple forward slashes, but in that case one cannot use regex modifiers. Alternatively, you may prefix the expression with :m, in which case the qname quoting convention is followed and one may provide a modifier suffix. Escaping within the delimiters is as one would expect for a regular expression, but note that you are writing the expression as a string rather than a regex literal, so you may have to double-escape.
:m
index matching
Index matching uses the string index function, so it only finds whether one literal string occurs as a substring of another -- the right as a substring of the left. There are three variants for the three most common uses of index matching:
|=
True if the left operand starts with the right operand.
=|=
True if the right operand occurs anywhere in the left.
=|
True if the right operand ends the left operand.
Boolean predicates combine various terms -- attributes, attribute tests, or tpath expressions -- via boolean operators:
!
not
True iff the attribute is undefined, the attribute test returns false, the expression returns no nodes, or the boolean expression is false.
&
and
True iff all conjoined operands are true.
||
or
True iff any of the conjoined operands is true.
Note that boolean or is two pipe characters. This is to disambiguate the path expression a|b from the boolean expression a||b.
a|b
a||b
;
one
True if one and only one of the conjoined operands is true. The expression
@a ; @b
behaves like ordinary exclusive or. But if more than two operands are conjoined this way, the entire expression is a uniqueness test.
( ... )
Groups the contained boolean operations. True iff they evaluate to true.
The normal precedence rules of logical operators applies to these:
() < ! < & < ; < ||
//foo[@bar] //foo[@bar(1, 'string', path, @attribute, @attribute = 'test')]
Attributes identify callbacks that evaluate a TPath::Context to see whether the respective attribute is defined for it. If the callback returns a defined value, the predicate is true and the candidate is accepted; otherwise, it is rejected.
As the second example above demonstrates, attributes may take arguments and these arguments may be numbers, strings, paths, other attributes, or attribute tests. Paths are evaluated relative to the candidate node being tested, as are attributes and attribute tests. A path argument is evaluated to the TPath::Context objects selected by this path relative to the candidate node.
Attribute parameters are enclosed within parentheses. Within these parentheses, they are delimited by commas. Space is optional around parameters.
For the standard attribute set available to all expressions, see TPath::Attributes::Standard. For the extended set that can be composed in, see TPath::Attributes::Extended.
There are various ways one can add bespoke attributes but the easiest is to add them to an individual forester via the add_attribute method:
add_attribute
my $forester = MyForester->new; $forester->add_attribute( 'foo' => sub { my ( $self, $context, @params) = @_; ... });
Another methods is to define attributes as annotated methods of the forester
sub foo :Attr { my ( $self, $context, @params) = @_; ... }
If this would cause a namespace collision or is not a possible method name, you can provide the attribute name as a parameter of the method attribute:
sub foo :Attr(problem:name) { my ( $self, $context, @params) = @_; ... }
Defining attributes as annotated methods is particularly useful if you wish to create an attribute library that you can mix into various foresters. In this case you define the attributes within a role instead of the forester itself.
package PimpedForester; use Moose; extends 'TPath::Forester'; with qw(TheseAttributes ThoseAttributes YonderAttributes Etc); sub tag { ... } sub children { ... }
Some trees, like HTML and XML parse trees, may have ad hoc attributes. Foresters for this sort of tree should override the default autoload_attribute method. This method expects an attribute name and an optional list of arguments and returns a code reference. The code reference in turn, when applied to a context and a list of context-specific arguments, must return the value of the given attribute in that context. For instance, the following implements HTML attribute autoloading providing these nodes have an attribute method that returns the value of a particular attribute at a given node, or undef when the attribute is undefined:
autoload_attribute
attribute
sub autoload_attribute { my ( $self, $name ) = @_; return sub { my ( $self, $ctx ) = @_; return $ctx->n->attribute($name); }; }
With this one could write expressions such as //div[@:style =|= 'width'] which auto-load the style attribute. Note the expression syntax: attributes whose names are preceded by an unescaped colon are supplied by the autoload_attribute method.
//div[@:style =|= 'width']
style
One could make this HTML implementation more efficient by memoizing autoload_attribute. For HTML attributes it doesn't make sense to further parameterize attribute generation -- all you need is the name -- so any attribute arguments are ignored during auto-loading.
There are three special attributes among the standard attributes that facilitate using variables in tpath expressions: @var, @v, and @clear_var. The first two are synonyms, so there are really only two functionally distinct variable attributes. The first two allow one to set or check the value of a particular variable. The last clears a variable, returning whatever value it had before clearing. The variables themselves live in a hash belonging to a particular expression.
@var
@v
@clear_var
One can use variables to obtain information from a selection other than a list of nodes. For example,
my $exp = $forester->path('/*[@v( "size", @tsize )][@v( "leaves", @size(leaf::*) )]'); $exp->select($tree); say 'number of nodes in the tree: ' . $exp->vars->{size}; say 'number of leaf nodes: ' . $exp->vars->{leaves};
One may also use variables to make later selections in an expression dependent on earlier selections.
my $exp = $forester->path('//foo[ @v( "bar", @quux ) ]//baz[ @quux = @v("bar") ]');
Finally, one may use variables to parameterize an expression:
for my $fruit qw(apple orange kumquat quince) { $exp->vars->{fruit} = $fruit; my @harvest = $exp->select($tree); deliver( $recipients->{$fruit}, @harvest ); }
There are four special selectors that cannot occur with predicates and may only be preceded by the / or null separators.
This is an abbreviation for self::*.
self::*
This is an abbreviation for parent::*.
parent::*
This selector selects the node, if any, with the given id. This same node can also be selected by //*[@id = 'foo'] but this is much less efficient.
//*[@id = 'foo']
This expression selects the root of the tree. It doesn't make much sense except as the first step in an expression.
This expression selects the node from which the current node was selected. For example, /a/b/:p will select the a node selected before the b node. How is this ever useful? Well, it lets one write expressions like
/a/b/:p
//a//b[@height = @at(/:p, 'depth')]
This selects all b nodes descended from a nodes where some a node the b node is descended from has the same depth as the b node's height.
One can iterate the :p selector to move different distances up the selection path and one can impose predicates on the selector to filter the selection.
//a//b//c//d[@height = @at(/:p+, 'depth')]
See also the previous:: axis.
previous::
TPath expressions may contain sub-paths consisting of grouped alternates and steps or sub-paths may be quantified as in regular expressions
//a(/b|/c)/d
//a?/b*/c+
//a(/b/c)+/d
//a(/b/c){3}/d
//a{3,}
//a{0,3}
//a{,3}
The last expression, {,3}, one does not see in regular expressions. It is the short form of {0,3}.
{,3}
{0,3}
Despite this similarity it should be remembered that tpath expression differ from regular expressions in that they always return all possible matches, not just the first match discovered or, for those regular expression engines that provide longest token matching or other optimality criteria, the optimal match. On the other hand, the first node selected will correspond to the first match using greedy repetition. And if you have optimality criteria you are free to re-rank the nodes selected and pick the first node by this ranking.
In some cases there may be nodes -- spaces, comments, hidden directories and files -- that you want your expressions to treat as invisible. To do this you add invisibility tests to the forester object that generates expressions.
my $forester = MyForester->new; $forester->add_test( sub { my ($forester, $node, $index) = @_; ... # return true if the node should be invisible });
One can put this in the forester's BUILD method to make them invisible to all instances of the class.
BUILD
For most uses, where tpath and xpath provide similar functionality they will behave identically. Where you may be led astray is in the semantics of separators beginning paths.
/foo/foo //foo//foo
In both tpath and xpath, when applied to the root of a tree the first expression will select the root itself if this root has the tag foo and the second will select all foo nodes, including the root if it bears this tag. This is notably different from the behavior of the second step in each path. The second /foo will select a foo child of the root node, not the root node itself, and the second //foo will select foo descendants of other foo nodes, not the nodes themselves.
/foo
//foo
Where the two formalisms may differ is in the nodes they return when these paths are applied to some sub-node. In xpath, /foo always refers to the root node, provided this is a foo node. In tpath it always refers to the node the path is applied to, provided it is a foo node. In tpath, if you require that the first step refer to the root node you must use the root selector :root. If you also require that this node bear the tag foo you must combine the root selector with the self:: axis.
self::
:root/self::foo
This is verbose, but then this is not likely to be a common requirement.
The tpath semantics facilitate the implementation of repetition, which is absent from xpath.
Where you may use a string literal -- 'foo', "foo", q("fo'o"), etc. -- you may also use a string concatenation. The string concatenation operator is ~. The arguments it may separate are string literals, numbers, mathematical expressions, attributes, or path expressions. Constants will be concatenated during compilation, so
'foo'
"foo"
q("fo'o")
~
//foo('a' ~ 1)
will compile to
//foo('a1')
The spaces are optional.
The actual Regexp::Grammars parser which defines TPath expressions is in TPath::Grammar. The crucial part, most likely, is the definition of the <name> rule which governs what you can put in tags and attribute names without escaping. The rule is
(\\.|[\p{L}\$_])(?>[\p{L}\$\p{N}_]|[-.:](?=[\p{L}_\$\p{N}])|\\.)*+ | <qname>
This means a tag or attribute name begins with a letter, the dollar sign, or an underscore, and is followed by these characters or numbers, or dashes, dots, or colons followed by these characters. And at any time one can violate this basic rule by escaping a character that would put one in violation with the backslash character, which thus cannot itself appear except when escaped.
One can also use a quoted expression, with either single or double quotes. The usual escaping convention holds, so "a\"a" would represent two a's with a " between them. However neither single nor double quotes may begin a path as this would make certain expressions ambiguous -- is a[@b = 'c'] comparing @b to a path or a literal?
a[@b = 'c']
@b
Finally, one can "quote" the entire expression following the qname convention, which is roughly:
qname
: [[:punct:]].+?[[:punct:]]
A quoted name begins with a colon followed by some delimiter character, which must be a POSIX punctuation mark. These are the symbols
<>[](){}/!"#$%&'*+,-.:;=?@^_`|~
Note that the backslash character is missing from that set. If the character after the colon is the first of one of the bracket pairs, the trailing delimiter must be the other member of the pair, so
:<a> :[a] :(a) :{a}
are correct but
:<a<
and so forth are bad. However,
:>a> :]a] :)a) :}a}
are all fine, as are
:;a; ::a: :-a-
and so forth. Within these delimiters the normal escaping convention holds: \ escapes the following character.
The qname convention improves readability in some instances by allowing one to avoid escapes. Since the qname convention commits you to 3 extra-name characters before any escapes, it is generally not advisable unless you otherwise would have to escape more than 3 characters or you feel that whatever escaping you would have to do would mar legibility. Double and single quotes make particularly legible qname delimiters if it comes to that. Compare
file\ name\ with\ spaces :"file name with spaces"
One uses the same number of characters in each case but the second is clearly easier on the eye. In this case the colon is necessary because " cannot begin a path expression.
Before or after most elements of tpath expressions one may put arbitrary whitespace or #-style comments.
# a path made more complicated than necessary //a # first look for a elements /*/* # find the grandchildren of these [0] # select the first-born grandchildren [ # and log their foo properties @log( @foo ) ]
There are some places where one cannot put whitespace or a comment: between a separator and a selector
// a # bad!
between an @ and an attribute name
@ foo # bad!
and between a repetition suffix and the element repeated
//a + # bad!
All the places where one may use the \ escape character to protect a special character in a string one may also use one of the escape sequences understood by tpath, which are just those understood by JSON. These are
\
The tab character.
The ASCII newline character -- decimal character 10 in the basic ASCII set. Note that this isn't the magic newline character in Perl that adapts to the operating system it finds itself on. This is just the 10th character in the ASCII set (excluding the null character).
The ASCII carriage return character, decimal character 13.
The ASCII form feed character.
The backspace character.
The vertical tab character. Why \v? Well, I figure it's important enough to somebody to be included in the JSON spec, so it's here too. This is character 11 in ASCII's decimal set.
I wrote tpath initially in Java (http://dfhoughton.org/treepath/) because I wanted a more convenient way to select nodes from parse trees. I've re-written it in Perl because I figured it might be handy and why not? Since I've been working on the Perl version I've added lots of features. Eventually I'll back port these to the Java version, but I haven't yet.
Tree::XPathEngine and Class::XPath provide similar functionality, though their aim is not to provide a generic tree path language but rather to provide a means of adapting XPath, designed with XML in mind, to non-XML trees. I have not actually used these modules, but if you are already familiar with XPath and your node names and whatnot comport with those of XPath, than these may better suit your needs.
If what you really want is to use XPath on XML in Perl, consider XML::XPath or XML::LibXML. If speed is your concern and you are able to use the latter, it's probably what you want.
TPath is fast enough as pure Perl tree path libraries go, but it has Moose's startup lag and its own conventions.
Thanks to Damian Conway for Regexp::Grammars, which makes it pleasant to write complicated parsers. Thanks to the Moose Cabal, who make it pleasant to write elaborate object oriented Perl. Without the use of roles I don't think I would have tried this. Thanks to Jon Rubin, who made me aware that tpath's index predicates weren't working like xpath's (since fixed). And thanks to my wife Paula, who has heard a lot more about tpath than is useful to her.
David F. Houghton <dfhoughton@gmail.com>
This software is copyright (c) 2013 by David F. Houghton.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
To install TPath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm TPath
CPAN shell
perl -MCPAN -e shell install TPath
For more information on module installation, please visit the detailed CPAN module installation guide.