Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

treeql - Query tree objects

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
package require snit
package require struct::list
package require struct::set
package require treeql ?1.3.2?

treeql objectname -tree tree ?-query query? ?-nodes nodes? ?args...?
qo query args...
qo result
qo discard

DESCRIPTION

This package provides objects which can be used to query and transform tree objects following the API of tree objects created by the package struct::tree.

The tree query and manipulation language used here, TreeQL, is inspired by Cost (See section References for more information).

treeql, the package, is a fairly thin query facility over tree-structured data types. It implements an ordered set of nodes (really a list) which are generated and filtered through the application of TreeQL operators to each node in turn.

API

TreeQL CLASS API

The command treeql is a snit::type which implements the Treeql Query Language. This means that it follows the API for class commands as specified by the package snit. Its general syntax is

TreeQL OBJECT API

As treeql has been implemented in snit all the standard methods of snit-based classes are available to the user and therefore not listed here. Please read the documentation for snit for what they are and what functionality they provide

The methods provided by the package treeql itself are listed and explained below.

The Tree Query Language

This and the following sections specify the Tree Query Language used by the query objects of this package in detail.

First we explain the general concepts underneath the language which are required to comprehend it. This is followed by the specifications for all the available query operators. They fall into eight categories, and each category has its own section.

  1. TreeQL Concepts

  2. Structural generators

  3. Attribute Filters

  4. Attribute Mutators

  5. Attribute String Accessors

  6. Sub-queries

  7. Node Set Operators

  8. Node Set Iterators

  9. Typed node support

TreeQL Concepts

The main concept which has to be understood is that of the node set. Each query object maintains exactly one such node set, and essentially all operators use it and input argument and for their result. This structure simply contains the handles of all nodes which are currently of interest to the query object. To name it a set is a bit of a misnomer, because

  1. A node (handle) can occur in the structure more than once, and

  2. the order of nodes in the structure is important as well. Whenever an operator processes all nodes in the node set it will do so in the order they occur in the structure.

Regarding the possible multiple occurrence of a node, consider a node set containing two nodes A and B, both having node P as their immediate parent. Application of the TreeQL operator "parent" will then add P to the new node set twice, once per node it was parent of. I.e. the new node set will then be {P P}.

Structural generators

All tree-structural operators locate nodes in the tree based on a structural relation ship to the nodes currently in the set and then replace the current node set with the set of nodes found Nodes which fulfill such a relationship multiple times are added to the result as often as they fulfill the relationship.

It is important to note that the found nodes are collected in a separate storage area while processing the node set, and are added to (or replacing) the current node set only after the current node set has been processed completely. In other words, the new nodes are not processed by the operator as well and do not affect the iteration.

When describing an operator the variable N will be used to refer to any node in the node set.

Attribute Filters

These operators filter the node set by reference to attributes of nodes and their properties. Filter means that all nodes not fulfilling the criteria are removed from the node set. In other words, the node set is replaced by the set of nodes fulfilling the filter criteria.

Attribute Mutators

These operators change node attributes within the underlying tree. In other words, all these operators have side effects.

Attribute String Accessors

These operators retrieve the values of node attributes from the underlying tree. The collected results are stored in the node set, but are not actually nodes.

In other words, they redefine the semantics of the node set stored by the query object to contain non-node data after their completion.

The query interpreter will terminate after it has finished processing one of these operators, silently discarding any later query elements. It also means that our talk about maintenance of a node set is not quite true. It is a node set while the interpreter is processing commands, but can be left as an attribute value set at the end of query processing.

Sub-queries

Sub-queries yield node sets which are then used to augment, reduce or replace the current node set.

Node Set Operators

These operators change the node set directly, without referring to the tree.

Node Set Iterators

Typed node support

These filters and accessors assume the existence of an attribute called @type, and are short-hand forms useful for cost-like tree query, html tree editing, and so on.

Examples

... TODO ...

References

  1. COST on the Tcler's Wiki.

  2. TreeQL on the Tcler's Wiki. Discuss this package there.

Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category treeql of the Tcllib Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

Cost, DOM, TreeQL, XPath, XSLT, structured queries, tree, tree query language

CATEGORY

Data structures

COPYRIGHT

Copyright © 2004 Colin McCormack
Copyright © 2004 Andreas Kupries