package querty
Build not yet checkedInstall
dune-project
Dependency
Authors
Maintainers
Sources
md5=0ffa7024073872bf1bea461dea7bac80
sha512=f2a8dbf7194439fa4c0d6304247a9923db4085a1671264c8866ae41bf0e7ad39bf7db18aa75e8b41de06c1158f3a7728d3cd7c8a804fca754b7bb72d92bc010f
doc/index.html
Querty
Querty is a library for incremental, demand-driven computation. You describe a computation as a set of typed queries and the rules that compute them. Querty runs only the rules needed for what you ask for, caches every result, and after an input changes recomputes only what that change affects.
It follows the design of Rock and Salsa.
Overview
There are four pieces:
- Input queries hold values you set from outside, such as file contents.
- Derived queries are computed by your rules. A rule may read inputs and fetch other derived queries.
- A database (
Querty.Make.db) stores input values, cached derived values and the dependencies each rule used last time it ran. Querty.Make.runevaluates a function that fetches queries, running rules on demand.
The rest of this page builds a small example: counting words across a set of files.
Defining queries
Queries are constructors of a GADT with two type parameters: the type of the query's value, and its kind, Querty.input or Querty.derrived. Constructors can take arguments; File "a.txt" and File "b.txt" are separate queries.
module Q = struct
type (_, _) t =
| Files : (string list, Querty.input) t
| File : string -> (string, Querty.input) t
| WordCount : string -> (int, Querty.derrived) t
| Total : (int, Querty.derrived) t
let rank : type a k. (a, k) t -> int = function
| Files -> 0
| File _ -> 1
| WordCount _ -> 2
| Total -> 3
let compare : type a b k1 k2.
(a, k1) t -> (b, k2) t -> (a, b) Querty.Order.t =
fun x y ->
let cmp_name a b =
let c = String.compare a b in
if c < 0 then Querty.Order.Lt else if c > 0 then Gt else Eq
in
match (x, y) with
| Files, Files -> Eq
| File a, File b -> cmp_name a b
| WordCount a, WordCount b -> cmp_name a b
| Total, Total -> Eq
| _ -> if rank x < rank y then Lt else Gt
let values_equal : type a k. (a, k) t -> a -> a -> bool =
fun key a b ->
match key with
| Files -> a = b
| File _ -> String.equal a b
| WordCount _ -> Int.equal a b
| Total -> Int.equal a b
end
module Engine = Querty.Make (Q)compare must be a total order on keys. The rank helper orders different constructors, so only same-constructor pairs need real comparison.
Return Eq only for the same query. Eq proves to the type checker that both keys have the same value type, and Querty relies on that proof when it looks values up in its cache. Returning Eq from a branch where both keys are matched against the same constructor is always correct.
values_equal decides when a recomputed value counts as unchanged; see How incrementality works.
Writing rules
A rule maps each derived query to its value. It gets inputs with Querty.Make.read and other derived queries with Querty.Make.fetch. Each call is recorded as a dependency of the rule that made it.
let rules : type a. (a, Querty.derrived) Q.t -> a = function
| WordCount name ->
print_endline ("counting " ^ name);
Engine.read (File name)
|> String.split_on_char ' '
|> List.filter (( <> ) "")
|> List.length
| Total ->
print_endline "summing";
Engine.read Files
|> List.map (fun name -> Engine.fetch (WordCount name))
|> List.fold_left ( + ) 0Rules must be deterministic and get everything they depend on through read and fetch. Querty cannot see anything else a rule looks at, such as a global variable or the file system, so changes to it will not cause a recomputation.
Dependencies are recorded each time a rule runs, so they can differ between runs. Total depends on whichever WordCount queries the current Files list names.
Running and updating
Create a database, set the inputs, and call Querty.Make.run:
let total db =
match Engine.run db ~rules (fun () -> Engine.fetch Total) with
| Ok n -> Printf.printf "total: %d\n" n
| Error (MissingInput _) -> print_endline "an input was not set"
| Error (Cycle _) -> print_endline "a query depends on itself"
let () =
let db = Engine.init () in
Engine.set_input db Files [ "a.txt"; "b.txt" ];
Engine.set_input db (File "a.txt") "hello world";
Engine.set_input db (File "b.txt") "one two three";
total db;
(* summing, counting a.txt, counting b.txt, total: 5 *)
total db;
(* total: 5 -- everything cached, no rule runs *)
Engine.set_input db (File "b.txt") "one two three four";
total db;
(* counting b.txt, summing, total: 6 *)
Engine.set_input db (File "a.txt") "hello world";
total db
(* counting a.txt, total: 6 -- count unchanged, so Total is not rerun *)Keep one database for the life of your program. A fresh database means recomputing everything.
Call Querty.Make.set_input between runs or from the top-level function given to run, never from inside a rule.
How incrementality works
The database has a revision counter. Querty.Make.set_input increments it whenever an input actually changes value.
For each derived query, the cache stores:
- its value;
- the dependencies its rule used, in the order it used them;
changed_at: the revision in which its value last changed;verified_at: the revision in which it was last confirmed up to date.
When a derived query is fetched:
- If it was verified in the current revision, the cached value is returned.
- Otherwise Querty walks its recorded dependencies in order, bringing each derived dependency up to date first. If any dependency changed after the query was last verified, the rule is run again.
- If no dependency changed, the cached value is kept and marked verified, without running the rule.
Early cutoff. When a rule reruns and Querty.QueryKey.values_equal says the new value equals the old one, the query keeps its old changed_at. Queries depending on it then see no change, and are not rerun. In the example, adding spaces to a.txt reruns WordCount "a.txt", but its count stays the same, so Total is not rerun.
Because dependencies are checked in the order they were recorded, and checking stops at the first change, Querty never brings a dependency up to date that the rule would not use on its next run.
Errors
Querty.Make.run returns Error in two cases:
MissingInput key: a rule read an input that was never set.keyis the first such input encountered.Cycle keys: a derived query fetched itself, directly or through other queries.keyslists every derived query being computed at that moment, which includes those forming the cycle, in unspecified order.
Values computed before the error stay cached and the database stays usable. Fix the cause (set the input, or change inputs so the cycle is no longer reached) and run again; only the remaining work is done.
Exceptions raised by your own rules propagate out of run unchanged.
API reference
Querty documents every type and function.