Zirql: extracting a shared query languageDRAFT

When implementing Zincite¹, I wanted a query language similar to the one I had built for Zirium. As with Zirium, I took inspiration from tools such as awk and jq, whose operations suit the data they work on: text records and fields for awk, JSON values for jq. I was particularly interested in writing checkers and transformations for MiniZinc data files: checking assumptions about an instance, changing its parameters, or making a smaller instance to investigate.

I soon decided it would be more fun to unify the two query languages than build another implementation. Selecting MiniZinc declarations and following MLIR operands need different operations, but filtering collections, naming intermediate results and combining conditions need the same language machinery. I also wanted improvements to those parts to be available in both tools.

The result is Zirql, a Rust library that both tools use to parse and evaluate queries. Each application supplies its data and the operations that make sense for it. I’ll call that application the host. The examples here use Zirql 0.2.0.

The documentation’s word example starts with a list of strings. I like it because the data needs little explanation, so we can concentrate on the language.

Start with four words#

Our input file, words.txt, contains:

ash apple birch apple

The host splits the file at whitespace and exposes the resulting array as words:

["ash", "apple", "birch", "apple"]

Both occurrences of apple stay in the array. The host leaves case and punctuation as written.

To find the words beginning with a, filter the array:

words | filter(w => starts_with(w, "a"))

The result is:

["ash", "apple", "apple"]

The predicate is a lambda: w names the current word, and filter includes it when the lambda returns true. Filtering keeps input order and duplicates. For a short predicate, _ can stand for the current argument:

words | filter(starts_with(_, "a"))

Zirql supplies starts_with, so the same operation works on filenames or names read from source code. It compares the strings exactly, so starts_with("Apple", "a") is false.

Instead of using a pipeline, a list can be constructed using a comprehension. Here is the same example using the MiniZinc comprehension style:²

[w | w in words where starts_with(w, "a")]

I prefer the filter when selecting entries without changing them. A comprehension becomes useful when constructing a different result for each entry, or combining several generators.

To put the selected words in alphabetical order, add a sorting stage:

words | filter(starts_with(_, "a")) | sort

Sorting gives ["apple", "apple", "ash"]. Add unique to remove duplicate spellings:

words | filter(starts_with(_, "a")) | sort | unique

["apple", "ash"]

Without the preceding sort, unique would keep each first occurrence in input order. For statistics, tally produces a dictionary of occurrence counts:

words | filter(starts_with(_, "a")) | tally

{"ash": 1, "apple": 2}

The keys follow first occurrence in the input, so ash comes before apple. These stages come from Zirql; the word host supplies the input.

Find neighbouring words#

The order of the input lets us ask which words occur next to each other. Suppose we want to count neighbours regardless of which word comes first. Build a set for each adjacent pair, then tally those sets:

[
    {words[i], words[i + 1]}
  | i in index_set(words)
        where i < length(words)
] | tally

The result is a dictionary from sets to counts. Here it is in Zirql notation:

{
    {"ash", "apple"}: 1,
    {"apple", "birch"}: 2
}

Array positions start at one. index_set(words) gives the valid positions, and the condition skips the last one, leaving room for words[i + 1]. Each position produces a set containing the two neighbouring words. The second and third pairs contain apple and birch in opposite orders, so tally counts them together.

Dictionary entries follow the first occurrence of each pair. Set equality compares membership, so {"apple", "birch"} and {"birch", "apple"} identify the same key. If we name the result neighbours, then neighbours[{"birch", "apple"}] gives 2.

Tuples, arrays and dictionaries can also be keys. JSON objects require string keys, so a host writing JSON must choose how to encode other kinds of key.

Sets also discard duplicate members. Two adjacent occurrences of apple would give the singleton set {"apple"}. Empty input and a single word both give an empty dictionary, {}.

The indexing makes the pairs adjacent. Two independent generators over words would visit every combination, including pairs that never appeared together.

From words to CSV tables#

The same filters can work on records with named fields. The CSV example loads each row as a record, using the header names as fields, and writes query results as JSON. We can use it to make a packing list from a couple of files.

Suppose we are bringing games to a friend’s house. games.csv records who owns each game, whether we are bringing it and whether it is packed. Kingdomino is already in the bag; Patchwork and NMBR 9 still need packing. Everdell and Cottage Garden are staying home (bring is "no"), although both are unpacked. The columns are title, owner, bring and packed.

Select the games still to pack#

With one input file, rows names its array of records. To find the games still to pack, select rows where bring is "yes" and packed is "no". Step through the filters to see which cells they check and which rows they return:

rows | filter(_.bring == "yes")
	| filter(_.packed == "no")

rows | filter(_.bring == "yes")
	| filter(_.packed == "no")

rows | filter(_.bring == "yes")
	| filter(_.packed == "no")

rows | filter(_.bring == "yes")
	| filter(_.packed == "no")

[  {"title": "Patchwork", "owner": "leo", "bring": "yes", "packed": "no"},  {"title": "NMBR 9", "owner": "mira", "bring": "yes", "packed": "no"}]

The first filter selects the games to bring; the second selects those still unpacked. _.bring and _.packed read fields on the current row. Checking only packed would also select Everdell and Cottage Garden. The result contains the whole Patchwork and NMBR 9 records, in file order.

The CSV host keeps cells as strings. It neither turns "01" into a number nor interprets "yes" as a Boolean.

To run this example, use Rust 1.88 or newer, clone the release and save the linked games.csv file in the checkout:

git clone --branch v0.2.0 --depth 1 https://github.com/zayenz/zirql.git
cd zirql
cargo run --locked --example csv -- '
rows | filter(_.bring == "yes")
    | filter(_.packed == "no")
' games.csv

Look up the owners in another file#

The game file identifies owners by ID. A second file, people.csv, maps these to names: mira is Mira and leo is Leo. Save it beside games.csv. Pass the files as games=games.csv and people=people.csv, and those names become bindings in the query.

let pending = games
	| filter(_.bring == "yes")
	| filter(_.packed == "no");
[
	{
		"game": g.title,
		"owner": p.name
	}
  | g in pending,
	p in people
		where p.id == g.owner
]

let pending = games
	| filter(_.bring == "yes")
	| filter(_.packed == "no");
[
	{
		"game": g.title,
		"owner": p.name
	}
  | g in pending,
	p in people
		where p.id == g.owner
]

let pending = games
	| filter(_.bring == "yes")
	| filter(_.packed == "no");
[
	{
		"game": g.title,
		"owner": p.name
	}
  | g in pending,
	p in people
		where p.id == g.owner
]

let pending = games
	| filter(_.bring == "yes")
	| filter(_.packed == "no");
[
	{
		"game": g.title,
		"owner": p.name
	}
  | g in pending,
	p in people
		where p.id == g.owner
]

[  {"game": "Patchwork", "owner": "Leo"},  {"game": "NMBR 9", "owner": "Mira"}]

let names the filtered array pending. For each game, p in people visits the owner rows, and where p.id == g.owner selects the matching row. The comprehension builds a record with the game’s title and the owner’s name.

Run the complete query with both named files:

cargo run --locked --example csv -- '
let pending = games
    | filter(_.bring == "yes")
    | filter(_.packed == "no");
[
    {
        "game": g.title,
        "owner": p.name
    }
  | g in pending,
    p in people
        where p.id == g.owner
]
' games=games.csv people=people.csv

The result names Leo for Patchwork, then Mira for NMBR 9. Each owner ID occurs once in this file. A missing ID would omit the game; repeated IDs would produce multiple matches. With several files, the query must use the table names rather than rows.

To turn these records into reminders, replace the record expression with p.name ++ ": bring " ++ g.title. ++ concatenates strings, giving ["Leo: bring Patchwork", "Mira: bring NMBR 9"].

Rewrite the records for a checklist#

The same file can supply a checklist for all three games we are bringing. Kingdomino needs to appear too, with its box already checked. Step through the construction to see how the source fields become checklist records:

[
	{
		"label": g.title,
		"checked": g.packed == "yes"
	}
  | g in rows
		where g.bring == "yes"
]

[
	{
		"label": g.title,
		"checked": g.packed == "yes"
	}
  | g in rows
		where g.bring == "yes"
]

[true, false, false]

[
	{
		"label": g.title,
		"checked": g.packed == "yes"
	}
  | g in rows
		where g.bring == "yes"
]

[  {"label": "Kingdomino", "checked": true},  {"label": "Patchwork", "checked": false},  {"label": "NMBR 9", "checked": false}]

The where condition selects the games to bring. Each record uses the title as its label and the comparison g.packed == "yes" as its Boolean checked value. This gives true for Kingdomino and false for Patchwork and NMBR 9. The host writes the new records as JSON for the checklist’s presentation code.

Run it with games.csv as the only input again:

cargo run --locked --example csv -- '
[
    {
        "label": g.title,
        "checked": g.packed == "yes"
    }
  | g in rows
        where g.bring == "yes"
]
' games.csv

The CSV host#

The Build the CSV host guide walks through the complete implementation. The host loads files, declares row fields from their headers and renders results as JSON. Zirql parses and evaluates the bindings, filters and comprehensions.

Putting Zirql in a Rust application#

For the Rust integration, I’ll return to the smaller word host. The complete example for this post reads a text file and evaluates an expression against its words. Save it as src/main.rs in a new Rust project, with this Cargo.toml:

[package]
name = "word-query"
version = "0.1.0"
edition = "2024"

[dependencies]
zirql = "0.2.0"

Use Rust 1.88 or newer. This builds the word-query command. Zirql is still early, so I expect the API to change as more applications use it.

With words.txt beside Cargo.toml, run:

cargo run -- words.txt 'words | filter(w => starts_with(w, "a"))'
cargo run -- words.txt 'length(words)'
cargo run -- words.txt

The first command selects ash, apple, apple; the second returns 4. Without an expression, the command tallies the neighbouring word sets. The host prints Rust’s Debug format, such as Integer(4) for a count. For readability, the results in this post use JSON or, for sets and dictionaries with set keys, Zirql notation.

The host structure stores the word array:

struct Words {
    words: ConstructedValue,
}

A ConstructedValue can hold strings, numbers, arrays, tuples, sets and dictionaries, including records with named fields. Loading the input creates an array of strings.

The parser uses ValueReaderHost to recognise words as a binding. During evaluation, ValueQueryHost supplies its type and value. For example, read_binding returns the array:

fn read_binding(
    &mut self,
    name: &str,
    range: &Range<usize>,
    budget: &mut Budget,
) -> Result<ConstructedValue, QueryError> {
    if name != "words" {
        return Err(QueryError::query(
            range.clone(),
            "unknown word-host binding",
        ));
    }
    copy_constructed_value(&self.words, budget, Location::Query(range.clone()))
}

The helper accounts for the copy in the query’s budget. The range locates any error in the query text.

The CSV host uses read_shared_binding to share immutable tables through Arc<ConstructedValue> without copying their rows. Zirql charges the query budget when it first reads a shared binding.

In the complete example, types declares words as an array of strings, even when the file is empty. The program then parses and evaluates the expression with the same budget:

let mut host = Words { words };
let mut reader = ArgumentReader::new(&query, 0)?;
let expression = read_value_expression(&mut reader, &mut host, &mut budget, 64)?;
reader.skip_whitespace();
let result = if reader.remaining().is_empty() {
    evaluate_query_value(&expression, &types, &mut host, &mut budget)
} else {
    Err(reader.error("expected the end of the expression"))
};
dispose_native_value(expression);
println!("{:#?}", result?);

Checking for the end of the input rejects trailing text after a valid expression. Evaluation checks names and known types, then returns a Rust value.

This host accepts a single expression. The embedding guide covers other entry points, including the preparation needed for named functions. A host with an existing parser can construct Zirql’s expression types directly.

The host chooses limits on work, produced values and nesting. Zirql applies them during parsing and evaluation, including nested queries. The host must account for its own work and limit file sizes separately; the budget does not measure time or memory.

Build a tool around the result#

An editor tool could use the word host to show where repeated words occur. We can change the query to produce that report without rebuilding the Rust application. Make a record for each occurrence, then group by spelling:

group_by(
    [
        {"word": words[i], "position": i}
      | i in index_set(words)
    ],
    "word"
)

Each group has a key and an items array. The group for apple contains both occurrences:

{
  "key": "apple",
  "items": [
    {"word": "apple", "position": 2},
    {"word": "apple", "position": 4}
  ]
}

Groups appear in the order their keys first occurred, and their members stay in input order.

The editor can inspect these Rust values directly and list words whose groups contain more than one item.

The host’s input policy would need more thought. Should Apple and apple count together? Is apple, a word with punctuation, or should the comma be removed? The loader can normalise the text, or the host can expose operations that let the query choose.

The positions above count words. To highlight them in an editor, the loader would also need to record their offsets in the original text. A host can instead expose native handles: references to objects in its own data model, with operations to read their text or follow relations between them. The documentation sketches these extensions; the runnable example here uses only strings.

This is how Zirium and Zincite work. Two operations called arith.addi can be different operations. Two declarations called capacity can belong to different scopes. Their queries keep the actual objects available until a projection asks for names or other report values. Those names can then be grouped just like words.

Find repeated operands in Zirium#

Zirium queries MLIR, an intermediate representation used by compilers. Suppose we want additions of the form x + x. Both operands must refer to the same value; printed names can be reused in different scopes.

Zirium’s query language writes it as:

let matches = match {
    from add in (input | filter(op("arith.addi")));
    bind lhs = operand(add, 0);
    bind rhs = operand(add, 1);
    where same_value(lhs, rhs);
};
let rows = matches | project(m, {
    "function": m.add | root(op("func.func")) | attr("sym_name") | one,
    "operation": m.add | names | one
});
report {"matches": rows, "count": length(rows)};

The from clause visits each addition, and the two bind clauses capture its operands. The same_value predicate checks whether they refer to the same value. The projection then reports the containing function’s name and the addition’s operation name.

On Zirium’s function example, this finds the addition in double and reports a count of 1. operand uses zero-based operand positions; ordinary Zirql value arrays use one-based positions.

Zirql manages the bindings and their scope; Zirium supplies operand, same_value and navigation to the containing function.

Compute over a tree#

A query can also define a recursive function. Zirium’s subtree-cost example has a root with no cost annotation and two children with costs 3 and 4:

fn subtree_cost(op: Operation) -> int {
    (cost_annotation(op) default 1) +
        sum([subtree_cost(child) | child in direct_children(op)])
}
let selected = filter(op("example.root"));
report subtree_cost(selected) | json

The answer is 8: one for the unannotated root, plus the two child costs. default 1 uses 1 when the annotation is absent; a malformed annotation is still an error.

The recursion follows the containment tree through direct_children. Following operand dependencies instead would traverse a graph and could revisit operations or encounter cycles. Recursive calls count against the same query budget.

Use Zincite as a Bash checker#

Checking data files was one reason I wanted queries in Zincite. The MiniZinc post puts assertions close to the data declarations; a query lets me run a check directly against an instance as well. For example, enough capacity in total does not imply enough at every position.

Save this as capacity.dzn:

demand = [2, 3, 4];
capacity = [6, 8, 5];

We want to double demand and fail the command if any position exceeds its capacity. Zirql’s require turns a failed condition into a query error. Save this query as capacity.zq:

let demand = items | filter(name("demand")) | values | one;
let capacity = items | filter(name("capacity")) | values | one;
let aligned_capacity = require(
    index_set(demand) = index_set(capacity),
    capacity, % Return this array when the indices match.
    "demand and capacity must have the same index set"
);
let scaled = [2 * d | d in demand];
require(
    forall(
        [scaled[i] <= aligned_capacity[i] | i in index_set(demand)]
    ),
    true, % Return true when every position fits.
    "Doubled demand exceeds capacity at one or more positions"
)

The comprehension compares each scaled demand with the capacity at that position. forall returns true when all comparisons pass.

Total scaled demand is 18 and total capacity is 19. But the third position needs 8 and has room for 5. Running zincite query --program-file capacity.zq capacity.dzn therefore fails with the message above and a nonzero exit status.

A query that returns false still completes successfully. Zincite reports evaluation errors with a nonzero exit status, so Bash can use require without parsing the result:

if zincite query --program-file capacity.zq capacity.dzn >/dev/null; then
    printf '%s\n' 'Capacity check passed'
else
    printf '%s\n' 'Capacity check failed' >&2
    exit 1
fi

The redirection suppresses the successful report; error diagnostics still go to stderr. With the data above, the script takes the failure branch. Change the third capacity from 5 to 8 and the check passes. A parse error or exhausted query budget also produces a nonzero status.

The first require checks the index sets before comparing entries, so equally long arrays with different indices cannot be paired accidentally. Zincite supplies the literal data; both checks use Zirql’s evaluator without running a MiniZinc solver. Zincite’s query guide develops the capacity example further, including input checks and detailed reports.

Conclusion#

Extracting Zirql has let me improve filtering, comprehensions and checks in one place and use them in both Zirium and Zincite. The CSV host gives me another way to try those ideas on ordinary data files.

I want to keep developing Zirql this way, through tools and examples that give the language something useful to do.