treeql(n)

📦
version 2.0 · 2 versions
, in fedora 43, fedora 44, nixos 26.05, nixpkgs unstable

treeql 💖 the Tree Query Language page, bestie

okay so welcome to treeql(n), aka the manual page for Tree Query Language — and yes it's a long one, we're doing this in parts, so grab a boba 🧋 and let's go. This is part 1 and there's more coming, don't you dare close the tab.

✨ NAME ✨

treeql — query tree objects 🎀 (yes that's it, that's the whole vibe, it queries trees, iconic)

🌸 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 🦋

So this package hands you objects that you can use to query and transform tree objects, following the exact same API as the tree objects that struct::tree makes. slay 💅

The tree query and manipulation language used in here is called TreeQL, and it's inspired by Cost (peep the References section for the deets, iykyk).

And treeql, the package itself? It's a fairly thin query facility sitting on top of tree-structured data types. What it actually does: it implements an ordered set of nodes (which is honestly just a list, we'll get into that 😭) that gets generated and filtered by applying TreeQL operators to each node in turn. periodt.

👑 API 👑

🧚 TREEQL CLASS API 🧚

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

treeql objectname -tree tree ?-query query? ?-nodes nodes? ?args...
  • treeql objectname -tree tree ?-query query? ?-nodes nodes? ?args... — this command creates a brand new tree query object and returns the fully qualified name of the object command as its result. The API that the returned command follows is described over in the section called TreeQL OBJECT API.

Some more deets on this one:

  • Every query object is tied to a single tree object. That's the object all queries get run against. one tree, one boo 🫶
  • If the option -nodes was specified, then its argument is treated as a list of nodes. That list is used to initialize the node set. It defaults to the empty list.
  • If the option -query was specified, then its argument gets interpreted as an object — the parent query of this query. It defaults to the object itself. All queries get interpreted in the environment of this object.
  • Any arguments that come after the options are treated as a query and run immediately, right after the node set has been initialized. It uses the exact same syntax for the query as the method query does.

The TreeQL operations available for all this are explained in the section about The Tree Query Language. That section also explains the term node set we keep throwing around up there. no gatekeeping here 💜

💅 TREEQL OBJECT API 💅

Since treeql is implemented in snit, all the standard methods of snit-based classes are available to you, so we're not listing them here (rude of us? maybe, but it's a whole other manual page). Please go read the docs for snit to find out what they are and what functionality they bring. 🫶

The methods that the treeql package itself provides are listed and explained right below.

  • qo query args... — this method interprets its arguments as a series of TreeQL operators and runs them left to right (i.e. first to last). Important: the first operator uses the node set currently known to the object to do its thing. In other words, the node set is not cleared or otherwise modified before the query runs. That's a feature bestie, it lets you run several queries one after the other and have each one use the results of the last. Any initialization has to be done by a query itself, using TreeQL operators. The result of the method is the node set after the last operator of the query has been executed.
Heads up 🚨 uncaught errors will leave the node set of the object in an intermediate state, matching whichever TreeQL operators ran successfully before the error happened. it's giving "half-finished smoothie", sorry.

So what that means in detail:

  1. The first argument is interpreted as the name of a query operator, then the number of arguments that operator needs is determined and taken from the arguments immediately following it.

Because of this, operators cannot have optional arguments — all arguments have to be present exactly as defined. Failing to do that will, at minimum, confuse the query interpreter, and more likely just cause errors. 😭

  1. The operator is applied to the current node set, yielding a new node set, and/or manipulating the tree object the query object is connected to.
  2. The arguments that got used (i.e. the operator name and its arguments) are removed from the list of method arguments, and then the whole process repeats from step 1, until the list of arguments is empty or an error occurs.

Look at this gorgeous example:

# q is the query object.

q query root children get data

# The above query
# - Resets the node set to the root node - root
# - Adds the children of root to the set - children
# - Replaces the node set with the       - get data
#   values for the attribute 'data',
#   for all nodes in the set which
#   have such an attribute.
# - And returns this information.

# Below we can see the same query, but rewritten
# to show the structure as it is seen by the query
# interpreter.

q query \
  root \
  children \
  get data

The operators of the TreeQL language available for this are explained in the section about The Tree Query Language. That section also explains the term node set used above. (yes we're repeating ourselves, it's called ✨being thorough✨)

  • qo result — this method returns a list containing the current node set.
  • qo discard — this method returns the current node set (just like the method result does), but it also destroys the query object (qo). Super useful when you're constructing and using sub-queries (%AUTO% objects that get immediately destroyed after use). bye bestie 👋

🌈 THE TREE QUERY LANGUAGE 🌈

This section and the ones after it specify the Tree Query Language used by the query objects of this package, in detail. no skimming allowed.

First we explain the general concepts underneath the language, because you genuinely need those to comprehend it. Then come 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

(okay yes, the list has nine entries for eight categories, we are not the ones who wrote it, moving on 💀)

🌸 TREEQL CONCEPTS 🌸

The main concept you have to understand is the node set. Every query object maintains exactly one of these, and basically every operator uses it as input argument and for its result. This structure simply contains the handles of all nodes that are currently of interest to the query object.

Now, calling 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 matters too. Whenever an operator processes all nodes in the node set, it does so in the order they occur in the structure.

About that multiple-occurrence thing: imagine a node set containing two nodes A and B, and both of them have node P as their immediate parent. Applying the TreeQL operator "parent" will then add P to the new node set twice — once per node it was parent of. So the new node set will then be {P P}. not a typo, it's just how it is 💅

🎀 STRUCTURAL GENERATORS 🎀

All tree-structural operators locate nodes in the tree based on a structural relationship 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 get added to the result as often as they fulfill the relationship. ok so duplicates are just part of the deal.

Important thing to note: the found nodes get collected in a separate storage area while the node set is being processed, and are added to (or replace) 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. no self-referencing chaos, we love boundaries 🫶

When describing an operator, the variable N is used to refer to any node in the node set.

  • ancestors — replaces the current node set with the ancestors for all nodes N in the node set, should N have a parent. In other words, nodes without a parent do not contribute to the new node set. In other words (yes, again), it uses all nodes on the path from node N to root, in this order (root last), for all nodes N in the node set. This includes the root, but not the node itself.
  • rootpath — replaces the current node set with the ancestors for all nodes N in the node set, should N have a parent. In other words, nodes without a parent do not contribute to the new node set. But in contrast to the operator ancestors, the nodes are added in reverse order, i.e. the root node first. 🌱
  • parent — replaces the current node set with the parent of node N, for all nodes N in the node set, should N have a parent. In other words, nodes without a parent do not contribute to the new node set.
  • children — replaces the current node set with the immediate children of node N, for all nodes N in the node set, should N have children. In other words, nodes without children do not contribute to the new node set.
  • left — replaces the current node set with the previous/left sibling for all nodes N in the node set, should N have siblings to the left. In other words, nodes without left siblings do not contribute to the new node set.
  • right — replaces the current node set with the next/right sibling for all nodes N in the node set, should N have siblings to the right. In other words, nodes without right siblings do not contribute to the new node set.
  • prev — replaces the current node set with all previous/left siblings of node N, for all nodes N in the node set, should N have siblings to the left. In other words, nodes without left siblings are ignored. The left sibling adjacent to the node is added first, and the leftmost sibling last (reverse tree order).

ok that's part 1 done, don't go anywhere, more parts are coming 💖✨

  • esib — okay so this one goes backwards through the sibling lineup 💅 For every node N in your node set, it swaps the set out for all the previous/left siblings of N — but only if N actually has siblings to the left. Translation: no left siblings = you're getting ignored, bestie, nothing happens for you. Order matters here and it's lowkey particular: the leftmost sibling gets added first, and the left sibling sitting right next to your node gets added last (that's tree order, iykyk).

Fun fact: the name is just shorthand for Earlier SIBling ✨

  • next — the mirror twin of esib 🪞 For every node N in the node set, replace the set with all its next/right siblings, as long as N has siblings to the right. Nodes with no right siblings contribute nothing to the new node set, periodt. The right sibling adjacent to the node comes first, and the rightmost sibling comes last (tree order again).
  • root — replaces the whole node set with a node set holding exactly one single node: the root of the tree 👑 That's it, that's the operator.
  • tree — replaces the current node set with a set containing every node in the tree 🌈 They get added in pre-order: parent first, then the children, and those children go left to right, first to last.
  • descendants — for every node N in the node set, replace the set with all the nodes inside the subtrees rooted at N — but only if N actually has children. No children = no contribution to the new node set 🙈

This is like the children operator but it goes deeper, covering the children of children too — i.e. all the proper descendants. And "rooted at N" means N itself does not get added to the new set — which, honestly, is already implied by the whole "proper descendants" thing.

  • subtree — like descendants but it does include node N itself 🫶 So:

For every node N in the node set, it replaces the current node set with the nodes of the subtree of N — as long as N has children. Nodes without children contribute nothing to the new node set. I.e. this is like the children operator, but covers the children of children, etc. as well. And "of N" means N itself is added to the new set. Slay, we love inclusivity 💖

  • forward — replaces the node set with all the nodes in the subtrees rooted at the right siblings of node N, for every N in the set — as long as N has right siblings, and they have children. So nodes without right siblings, and those right siblings without children, get ignored 🚫

This is exactly equivalent to the operator sequence:

next descendants
  • later — this is just an alias for the operator forward ✨
  • backward — replaces the node set with the nodes in the flattened previous subtrees, in reverse tree order 🔄

It's nearly equivalent to the operator sequence:

prev descendants

The only difference: this one uses the nodes in reverse order.

  • earlier — replaces the node set with the nodes in the flattened previous subtrees, in tree order.

This is equivalent to the operator sequence:

prev subtree

🌸 ATTRIBUTE FILTERS 🌸

These operators filter the node set by looking at nodes' attributes and their properties. "Filter" here means: any node that doesn't meet the criteria gets yeeted out of the node set 💀 In other words, the node set gets replaced by the set of nodes that do fulfil the filter criteria.

  • hasatt attr — trims the node set down to only the nodes that have an attribute named attr.
  • withatt attr value — trims the node set to nodes that have an attribute named attr, and where that attribute's value equals value. (The == operator here is string equal -nocase.)
  • withatt! attr val — same as withatt, except every single node in the node set has to have the attribute, and the == operator is plain string equal — no -nocase. If they don't have the attribute, the operator fails with an error 😭
  • atoff attr vals — trims the node set to nodes that have an attribute named attr where that attribute's value is contained in the list vals of legal values. The contained-in operator used here does glob matching (using the attribute value as the pattern) and ignores the case of the attribute value — but not for the elements of vals.
  • attmatch attr match — same as withatt, but string match is used as the == operator, and match is the pattern being checked against.

Careful bestie, this one's got a catch 👀 match is interpreted as a partial argument list for string match. Which means it's read as a list containing the pattern, and the pattern element can be preceded by options understood by string match, like -nocase. This matters especially if your pattern has spaces in it — it has to be wrapped in a list so this operator interprets it correctly.

💅 ATTRIBUTE MUTATORS 💅

These operators change node attributes in the underlying tree. In other words: all of them have side effects 😳 Yeah. They're not just looking, they're touching.

  • set attr val — sets the attribute attr to the value val, for every node N in the node set. The operator will fail if a node doesn't have an attribute named attr, and the tree gets left in a partially modified state 😭 Be careful out there.
  • unset attr — unsets the attribute attr, for every node N in the node set. Same deal: the operator will fail if a node doesn't have an attribute named attr, and the tree gets left in a partially modified state.

🎀 ATTRIBUTE STRING ACCESSORS 🎀

These operators pull the values of node attributes out of the underlying tree. The collected results get stored in the node set — but they're not actually nodes ✨

In other words, once they finish, they redefine the semantics of the node set stored by the query object so it holds non-node data. Wild, I know.

The query interpreter terminates after it finishes processing one of these operators, silently discarding any later query elements 🫢 Which also means all our cute talk about "maintaining a node set" isn't quite true. It is a node set while the interpreter is chugging through commands, but it can be left as an attribute value set once query processing wraps up.

  • string op attr — applies the string operator op to the attribute named attr, for every node N in the node set, collects the results of that application, and drops them into the node set.

The operator will fail if a node doesn't have an attribute named attr.

The argument op is interpreted as a partial argument list for the builtin command string. Its first word has to be any of the sub-commands understood by string. That has to be followed by all the arguments required for the subcommand — except the last one. That last argument is supplied by the attribute value 💖

  • get pattern — for every node N in the node set, it finds all their attributes with names matching the glob pattern, then the values of those attributes, and at last it replaces the node set with the list of those attribute values.
  • attlist — this is just a convenience definition for the operator getvals * 💫 In other words, it replaces the node set with a list of the attribute values for all attributes, for all nodes N in the node set.
  • attrs glob — replaces the current node set with a list of attribute lists — one attribute list per node, for all nodes N in the node set.
  • attval attname — reduces the current node set with the operator hasatt, and then replaces it with a list containing the values of the attribute named attname, for all nodes N in the node set.

🦋 SUB-QUERIES 🦋

Sub-queries produce node sets that then get used to augment, reduce, or replace the current node set. Little queries doing big things, honestly iconic ✨

  • andq query — replaces the node set with the set-intersection of the node set generated by the sub-query query and itself.

Running the sub-query uses the current node set as its own initial node set.

  • orq query — replaces the node set with the set-union of the node set generated by the sub-query query and itself. Duplicate nodes get removed 🧹

Running the sub-query uses the current node set as its own initial node set.

  • notq query — replaces the node set with the set of nodes generated by the sub-query query that are also not in the current node set. In other words: the set difference of itself and the node set the sub-query generated.

Running the sub-query uses the current node set as its own initial node set.

👑 NODE SET OPERATORS 👑

These operators change the node set directly — no tree required, they're independent like that 💅

  • unique — removes duplicate nodes from the node set while preserving order. In other words, the earliest occurrence of a node handle is preserved, and every other occurrence gets removed.
  • select — replaces the current node set with a node set containing only the first node from the current node set.
  • transform query var body — first it interprets the sub-query query, using the current node set as its initial node set. Then it iterates over the result of that query, binding the handle of each node to the variable named in var, and executing the script body. The collected results of those executions become the new node set, replacing the current one ✨

The script body is executed in the context of the caller.

  • map var body — iterates over the current node set, binding the handle of each node to the variable named in var, and executing the script body. The collected results of those executions become the new node set, replacing the current one.

The script body is executed in the context of the caller.

  • quote val — appends the literal value val to the current node set.
  • replace val — replaces the current node set with the literal list value val.

🌈 NODE SET ITERATORS 🌈

  • foreach query var body — interprets the sub-query query, then does the equivalent of the operator over on the nodes in the node set that query created. The current node set is not changed — except through side effects coming from the script body 👀

The script body is executed in the context of the caller.

  • with query body — interprets the query, then runs the script body on the node set that query generated. And at last, it restores the current node set to exactly how it was before the query ran 🫶 So it's a little sneak peek that cleans up after itself, we love a tidy queen.

The script body is executed in the context of the caller.

  • over var body — this one runs the script body once for every single node in your node set, and it binds the variable named by var to the name of whichever node we're currently vibing on. The body runs in the context of the caller. It's giving builtin foreach, bestie — just with the node set as the list you're iterating over. And the results of running body? Ignored. Not collected, not returned, just ✨ ignored ✨.
  • delete — deletes every node in the current node set from the tree. Gone. Poof. 💅

✨ TYPED NODE SUPPORT ✨

Okay so these filters and accessors are all built on the assumption that there's an attribute named @type hanging around somewhere. They're shorthand forms, and they're highkey useful for cost-like tree query, html tree editing, and so on. 🦋

nodetype

Returns the node type of nodes. It's an attribute string accessor, and it's literally equivalent to:

get @type

oftype t

Shrinks the node set down to just the nodes whose type equals t. Letter case? Ignored, we don't care about it here. 🙈

nottype t

Same energy, opposite direction: shrinks the node set to nodes whose type is not equal to t, letter case ignored.

oftypes attrs

Reduces the set to nodes whose @type is an element in the list attrs of types. Important detail: the value of @type gets used as a glob pattern, and here letter case is relevant. Not ignored. Relevant. Pay attention bestie 🎀

🌸 EXAMPLES 🌸

... TODO ...

Not the examples section being literally ... TODO ... 😭💀 the authors said "we'll do it later" and never came back. Iconic behaviour honestly.

💜 REFERENCES 💜

  1. COST — http://wiki.tcl.tk/COST on the Tcler's Wiki.
  2. TreeQL — http://wiki.tcl.tk/treeql on the Tcler's Wiki. Discuss this package there, fr fr. 👑

🫶 BUGS, IDEAS, FEEDBACK 🫶

This document, and the package it describes, will undoubtedly contain bugs and other problems. No cap. Please report such in the category treeql of the Tcllib Trackers at http://core.tcl.tk/tcllib/reportlist. Also please report any ideas for enhancements you may have for either the package and/or the documentation — we want them all. ✨

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. To attach something, go to the Edit form of the ticket immediately after its creation, and then use the left-most button in the secondary navigation bar. That's the one. 👈

⭐ KEYWORDS ⭐

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

🌈 CATEGORY 🌈

Data structures

Copyright (c) 2004 Colin McCormack <coldstore@users.sourceforge.net>

Copyright (c) 2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>

And that's the whole page bestie — this lil masterpiece is from the tcllib package, version 1.3.2, and it's the treeql(n) manual page. Go build some trees, query them beautifully, and remember: every node deserves main character energy. 🧚💖

📦 where this page comes from