1treeql(n) Tree Query Language treeql(n)
2______________________________________________________________________________
6
8 treeql - Query tree objects
9
11 package require Tcl 8.2
12 package require snit
14 package require struct::list
16 package require struct::set
18 package require treeql ?1.3.1?
20 treeql objectname -tree tree ?-query query? ?-nodes nodes? ?args...?
22 qo query args...
24 qo result
26 qo discard
28_________________________________________________________________
30
32 This package provides objects which can be used to query and transform
33 tree objects following the API of tree objects created by the package
34 struct::tree.
35 The tree query and manipulation language used here, TreeQL, is inspired
37 by Cost (See section References for more information).
38 treeql, the package, is a fairly thin query facility over tree-struc‐
40 tured data types. It implements an ordered set of nodes (really a
41 list) which are generated and filtered through the application of
42 TreeQL operators to each node in turn.
43
45 TREEQL CLASS API
46 The command treeql is a snit::type which implements the Treeql Query
47 Language. This means that it follows the API for class commands as
48 specified by the package snit. Its general syntax is
49 treeql objectname -tree tree ?-query query? ?-nodes nodes? ?args...?
51 The command creates a new tree query object and returns the
52 fully qualified name of the object command as its result. The
53 API the returned command is following is described in the sec‐
54 tion TreeQL OBJECT API
55 Each query object is associated with a single tree object. This
57 is the object all queries will be run against.
58 If the option -nodes was specified then its argument is treated
60 as a list of nodes. This list is used to initialize the node
61 set. It defaults to the empty list.
62 If the option -query was specified then its argument will be
64 interpreted as an object, the parent query of this query. It
65 defaults to the object itself. All queries will be interpreted
66 in the environment of this object.
67 Any arguments coming after the options are treated as a query
69 and run immediately, after the node set has been initialized.
70 This uses the same syntax for the query as the method query.
71 The operations of the TreeQL available for this are explained in
73 the section about The Tree Query Language. This section also
74 explains the term node set used above.
75 TREEQL OBJECT API
77 As treeql has been implemented in snit all the standard methods of
78 snit-based classes are available to the user and therefore not listed
79 here. Please read the documentation for snit for what they are and what
80 functionality they provide
81 The methods provided by the package treeql itself are listed and
83 explained below.
84 qo query args...
86 This method interprets its arguments as a series of TreeQL oper‐
87 ators and interpretes them from the left to right (i.e. first to
88 last). Note that the first operator uses the node set currently
89 known to the object to perform its actions. In other words, the
90 node set is not cleared, or modified in other ways, before the
91 query is run. This allows the user to run several queries one
92 after the other and have each use the results of the last. Any
93 initialization has to be done by any query itself, using TreeQL
94 operators. The result of the method is the node set after the
95 last operator of the query has been executed.
96 Note that uncaught errors will leave the node set of the object
98 in an intermediate state, per the TreeQL operators which were
99 executed successfully before the error occurred.
100 The above means in detail that:
102 [1] The first argument is interpreted as the name of a query
104 operator, the number of arguments required by that opera‐
105 tor is then determined, and taken from the immediately
106 following arguments.
107 Because of this operators cannot have optional arguments,
109 all arguments have to be present as defined. Failure to
110 do this will, at least, confuse the query interpreter,
111 but more likely cause errors.
112 [2] The operator is applied to the current node set, yielding
114 a new node set, and/or manipulating the tree object the
115 query object is connected to.
116 [3] The arguments used (i.e. operator name and arguments) are
118 removed from the list of method arguments, and then the
119 whole process is repeated from step [1], until the list
120 of arguments is empty or an error occurred.
121 # q is the query object.
124 q query root children get data
126 # The above query
128 # - Resets the node set to the root node - root
129 # - Adds the children of root to the set - children
130 # - Replaces the node set with the - get data
131 # values for the attribute 'data',
132 # for all nodes in the set which
133 # have such an attribute.
134 # - And returns this information.
135 # Below we can see the same query, but rewritten
137 # to show the structure as it is seen by the query
138 # interpreter.
139 q query \\
141 root \\
142 children \\
143 get data
144 The operators of the TreeQL language available for this are explained
147 in the section about The Tree Query Language. This section also
148 explains the term node set used above.
149 qo result
151 This method returns a list containing the current node set.
152 qo discard
154 This method returns the current node set (like method result),
155 but also destroys the query object (qo). This is useful when
156 constructing and using sub-queries (%AUTO% objects immediately
157 destroyed after use).
158
160 This and the following sections specify the Tree Query Language used by
161 the query objects of this package in detail.
162 First we explain the general concepts underneath the language which are
164 required to comprehend it. This is followed by the specifications for
165 all the available query operators. They fall into eight categories, and
166 each category has its own section.
167 [1] TreeQL Concepts
169 [2] Structural generators
171 [3] Attribute Filters
173 [4] Attribute Mutators
175 [5] Attribute String Accessors
177 [6] Sub-queries
179 [7] Node Set Operators
181 [8] Node Set Iterators
183 [9] Typed node support
185 TREEQL CONCEPTS
187 The main concept which has to be understood is that of the node set.
188 Each query object maintains exactly one such node set, and essentially
189 all operators use it and input argument and for their result. This
190 structure simply contains the handles of all nodes which are currently
191 of interest to the query object. To name it a set is a bit of a mis‐
192 nomer, because
193 [1] A node (handle) can occur in the structure more than once, and
195 [2] the order of nodes in the structure is important as well. When‐
197 ever an operator processes all nodes in the node set it will do
198 so in the order they occur in the structure.
199 Regarding the possible multiple occurrence of a node, consider a node
201 set containing two nodes A and B, both having node P as their immediate
202 parent. Application of the TreeQL operator "parent" will then add P to
203 the new node set twice, once per node it was parent of. I.e. the new
204 node set will then be {P P}.
205 STRUCTURAL GENERATORS
207 All tree-structural operators locate nodes in the tree based on a
208 structural relation ship to the nodes currently in the set and then
209 replace the current node set with the set of nodes found Nodes which
210 fulfill such a relationship multiple times are added to the result as
211 often as they fulfill the relationship.
212 It is important to note that the found nodes are collected in a sepa‐
214 rate storage area while processing the node set, and are added to (or
215 replacing) the current node set only after the current node set has
216 been processed completely. In other words, the new nodes are not pro‐
217 cessed by the operator as well and do not affect the iteration.
218 When describing an operator the variable N will be used to refer to any
220 node in the node set.
221 ancestors
223 Replaces the current node set with the ancestors for all nodes N
224 in the node set, should N have a parent. In other words, nodes
225 without a parent do not contribute to the new node set. In other
226 words, uses all nodes on the path from node N to root, in this
227 order (root last), for all nodes N in the node set. This
228 includes the root, but not the node itself.
229 rootpath
231 Replaces the current node set with the ancestors for all nodes N
232 in the node set, should N have a parent. In other words, nodes
233 without a parent do not contribute to the new node set. In con‐
234 trast to the operator ancestors the nodes are added in reverse
235 order however, i.e. the root node first.
236 parent Replaces the current node set with the parent of node N, for all
238 nodes N in the node set, should N have a parent. In other words,
239 nodes without a parent do not contribute to the new node set.
240 children
242 Replaces the current node set with the immediate children of
243 node N, for all nodes N in the node set, should N have children.
244 In other words, nodes without children do not contribute to the
245 new node set.
246 left Replaces the current node set with the previous/left sibling for
248 all nodes N in the node set, should N have siblings to the left.
249 In other words, nodes without left siblings do not contribute to
250 the new node set.
251 right Replaces the current node set with the next/right sibling for
253 all nodes N in the node set, should N have siblings to the
254 right. In other words, nodes without right siblings do not con‐
255 tribute to the new node set.
256 prev Replaces the current node set with all previous/left siblings of
258 node N, for all nodes N in the node set, should N have siblings
259 to the left. In other words, nodes without left siblings are
260 ignored. The left sibling adjacent to the node is added first,
261 and the leftmost sibling last (reverse tree order).
262 esib Replaces the current node set with all previous/left siblings of
264 node N, for all nodes N in the node set, should N have siblings
265 to the left. In other words, nodes without left siblings are
266 ignored. The leftmost sibling is added first, and the left sib‐
267 ling adjacent to the node last (tree order).
268 The method name is a shorthand for Earlier SIBling.
270 next Replaces the current node set with all next/right siblings of
272 node N, for all nodes N in the node set, should N have siblings
273 to the right. In other words, nodes without right siblings do
274 not contribute to the new node set. The right sibling adjacent
275 to the node is added first, and the rightmost sibling last (tree
276 order).
277 root Replaces the current node set with a node set containing a sin‐
279 gle node, the root of the tree.
280 tree Replaces the current node set with a node set containing all
282 nodes found in the tree. The nodes are added in pre-order (par‐
283 ent first, then children, the latter from left to right, first
284 to last).
285 descendants
287 Replaces the current node set with the nodes in all subtrees
288 rooted at node N, for all nodes N in the node set, should N have
289 children. In other words, nodes without children do not contrib‐
290 ute to the new node set.
291 This is like the operator children, but covers the children of
293 children as well, i.e. all the proper descendants. "Rooted at N"
294 means that N itself is not added to the new set, which is also
295 implied by proper descendants.
296 subtree
298 Like operator descendants, but includes the node N. In other
299 words:
300 Replaces the current node set with the nodes of the subtree of
302 node N, for all nodes N in the node set, should N have children.
303 In other words, nodes without children do not contribute to the
304 new node set. I.e this is like the operator children, but covers
305 the children of children, etc. as well. "Of N" means that N
306 itself is added to the new set.
307 forward
309 Replaces the current node set with the nodes in the subtrees
310 rooted at the right siblings of node N, for all nodes N in the
311 node set, should N have right siblings, and they children. In
312 other words, nodes without right siblings, and them without
313 children are ignored.
314 This is equivalent to the operator sequence
316 next descendants
317 later This is an alias for the operator forward.
319 backward
321 Replaces the current node set with the nodes in the flattened
322 previous subtrees, in reverse tree order.
323 This is nearly equivalent to the operator sequence
325 prev descendants
326 The only difference is that this uses the nodes in reverse
327 order.
328 earlier
330 Replaces the current node set with the nodes in the flattened
331 previous subtrees, in tree order.
332 This is equivalent to the operator sequence
334 prev subtree
335 ATTRIBUTE FILTERS
337 These operators filter the node set by reference to attributes of nodes
338 and their properties. Filter means that all nodes not fulfilling the
339 criteria are removed from the node set. In other words, the node set is
340 replaced by the set of nodes fulfilling the filter criteria.
341 hasatt attr
343 Reduces the node set to nodes which have an attribute named
344 attr.
345 withatt attr value
347 Reduces the node set to nodes which have an attribute named
348 attr, and where the value of that attribute is equal to value
349 (The "==" operator is string equal -nocase).
350 withatt! attr val
352 This is the same as withatt, but all nodes in the node set have
353 to have the attribute, and the "==" operator is string equal,
354 i.e. no -nocase. The operator will fail with an error if they
355 don't have the attribute.
356 attof attr vals
358 Reduces the node set to nodes which which have an attribute
359 named attr and where the value of that attribute is contained in
360 the list vals of legal values. The contained-in operator used
361 here does glob matching (using the attribute value as pattern)
362 and ignores the case of the attribute value, but not for the
363 elements of vals.
364 attmatch attr match
366 Same as withatt, but string match is used as the "==" operator,
367 and match is the pattern checked for.
368 Note that match is a interpreted as a partial argument list for
370 string match. This means that it is interpreted as a list con‐
371 taining the pattern, and the pattern element can be preceded by
372 options understand by string match, like -nocase. This is espe‐
373 cially important should the pattern contain spaces. It has to be
374 wrapped into a list for correct interpretation by this operator
375 ATTRIBUTE MUTATORS
377 These operators change node attributes within the underlying tree. In
378 other words, all these operators have side effects.
379 set attr val
381 Sets the attribute attr to the value val, for all nodes N in the
382 node set. The operator will fail if a node does not have an
383 attribute named attr. The tree will be left in a partially modi‐
384 fied state.
385 unset attr
387 Unsets the attribute attr, for all nodes N in the node set. The
388 operator will fail if a node does not have an attribute named
389 attr. The tree will be left in a partially modified state.
390 ATTRIBUTE STRING ACCESSORS
392 These operators retrieve the values of node attributes from the under‐
393 lying tree. The collected results are stored in the node set, but are
394 not actually nodes.
395 In other words, they redefine the semantics of the node set stored by
397 the query object to contain non-node data after their completion.
398 The query interpreter will terminate after it has finished processing
400 one of these operators, silently discarding any later query elements.
401 It also means that our talk about maintenance of a node set is not
402 quite true. It is a node set while the interpreter is processing com‐
403 mands, but can be left as an attribute value set at the end of query
404 processing.
405 string op attr
407 Applies the string operator op to the attribute named attr, for
408 all nodes N in the node set, collects the results of that appli‐
409 cation and places them into the node set.
410 The operator will fail if a node does not have an attribute
412 named attr.
413 The argument op is interpreted as partial argument list for the
415 builtin command string. Its first word has to be any of the
416 sub-commands understood by string. This has to be followed by
417 all arguments required for the subcommand, except the last.
418 that last argument is supplied by the attribute value.
419 get pattern
421 For all nodes N in the node set it determines all their
422 attributes with names matching the glob pattern, then the values
423 of these attributes, at last it replaces the node set with the
424 list of these attribute values.
425 attlist
427 This is a convenience definition for the operator getvals *. In
428 other words, it replaces the node set with a list of the
429 attribute values for all attributes for all nodes N in the node
430 set.
431 attrs glob
433 Replaces the current node set with a list of attribute lists,
434 one attribute list per for all nodes N in the node set.
435 attval attname
437 Reduces the current node set with the operator hasatt, and then
438 replaces it with a list containing the values of the attribute
439 named attname for all nodes N in the node set.
440 SUB-QUERIES
442 Sub-queries yield node sets which are then used to augment, reduce or
443 replace the current node set.
444 andq query
446 Replaces the node set with the set-intersection of the node set
447 generated by the sub-query query and itself.
448 The execution of the sub-query uses the current node set as its
450 own initial node set.
451 orq query
453 Replaces the node set with the set-union of the node set gener‐
454 ated by the sub-query query and itself. Duplicate nodes are
455 removed.
456 The execution of the sub-query uses the current node set as its
458 own initial node set.
459 notq query
461 Replaces the node set with the set of nodes generated by the
462 sub-query query which are also not in the current node set. In
463 other word the set difference of itself and the node set gener‐
464 ated by the sub-query.
465 The execution of the sub-query uses the current node set as its
467 own initial node set.
468 NODE SET OPERATORS
470 These operators change the node set directly, without referring to the
471 tree.
472 unique Removes duplicate nodes from the node set, preserving order. In
474 other words, the earliest occurrence of a node handle is pre‐
475 served, every other occurrence is removed.
476 select Replaces the current node set with a node set containing only
478 the first node from the current node set
479 transform query var body
481 First it interprets the sub-query query, using the current node
482 set as its initial node set. Then it iterates over the result
483 of that query, binding the handle of each node to the variable
484 named in var, and executing the script body. The collected
485 results of these executions is made the new node set, replacing
486 the current one.
487 The script body is executed in the context of the caller.
489 map var body
491 Iterates over the current node set, binding the handle of each
492 node to the variable named in var, and executing the script
493 body. The collected results of these executions is made the new
494 node set, replacing the current one.
495 The script body is executed in the context of the caller.
497 quote val
499 Appends the literal value val to the current node set.
500 replace val
502 Replaces the current node set with the literal list value val.
503 NODE SET ITERATORS
505 foreach query var body
506 Interprets the sub-query query, then performs the equivalent of
507 operator over on the nodes in the node set created by that
508 query. The current node set is not changed, except through side
509 effects from the script body.
510 The script body is executed in the context of the caller.
512 with query body
514 Interprets the query, then runs the script body on the node set
515 generated by the query. At last it restores the current node set
516 as it was before the execution of the query.
517 The script body is executed in the context of the caller.
519 over var body
521 Executes the script body for each node in the node set, with the
522 variable named by var bound to the name of the current node.
523 The script body is executed in the context of the caller.
524 This is like the builtin foreach, with the node set as the
526 source of the list to iterate over.
527 The results of executing the body are ignored.
529 delete Deletes all the nodes contained in the current node set from the
531 tree.
532 TYPED NODE SUPPORT
534 These filters and accessors assume the existence of an attribute called
535 @type, and are short-hand forms useful for cost-like tree query, html
536 tree editing, and so on.
537 nodetype
539 Returns the node type of nodes. Attribute string accessor. This
540 is equivalent to
541 get @type
542 oftype t
544 Reduces the node set to nodes whose type is equal to t, with
545 letter case ignored.
546 nottype t
548 Reduces the node set to nodes whose type is not equal to t, with
549 letter case ignored.
550 oftypes attrs
552 Reduces set to nodes whose @type is an element in the list attrs
553 of types. The value of @type is used as a glob pattern, and let‐
554 ter case is relevant.
555
558 [1] COST [http://wiki.tcl.tk/COST] on the Tcler's Wiki.
559 [2] TreeQL [http://wiki.tcl.tk/treeql] on the Tcler's Wiki. Discuss
561 this package there.
562
564 This document, and the package it describes, will undoubtedly contain
565 bugs and other problems. Please report such in the category treeql of
566 the Tcllib SF Trackers [http://source‐
567 forge.net/tracker/?group_id=12883]. Please also report any ideas for
568 enhancements you may have for either package and/or documentation.
569
571 Cost, DOM, TreeQL, XPath, XSLT, structured queries, tree, tree query
572 language
573
575 Copyright (c) 2004 Colin McCormack <coldstore@users.sourceforge.net>
576 Copyright (c) 2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>
577treeql 1.3.1 treeql(n)