Overview

askl answers questions about code: which functions call this one, where this string occurs, what a module contains. A query names patterns and nests them; the engine resolves the names against an index of one or more uploaded projects and returns a graph — the symbols that matched, and the reference and containment edges among them.

These pages are long-form technical documents about how that happens — algorithms, data models, correctness invariants, and the trade-offs that shaped them. They are aimed at contributors, and at users who want a full picture of what happens when they run a query; the Askl Syntax Reference is the right first stop for using the language.

The life of a query link

Before any of the design questions, it helps to know what actually runs. A query is a sequence of statements, and statements are the only time axis the language has: they run in source order, one after another. Nesting inside a statement is the other axis: it states what the nested parts must have evidence of in each other, and the whole statement resolves together.

Parsing turns the text into a forest of substatements. Each one carries a command — its bag of verbs, folded in source order into a single filter predicate and a single combined populate (Queries and their Meaning). Two structural rules are checked before anything runs: every binding component must contain an anchor, so that a query cannot ask for “everything” by accident, and a @label may only reference an earlier statement.

Each statement then runs three phases before the next one starts (Evaluating the Fixpoint):

1. Materialise. Commands that produce content — search, loc, layer { … } — write their rows into new layers, which become visible to every later statement. Those layers are the statement’s materialisation, and each is stored and named separately (Partitioning a Materialisation has the split, Layer Keys and Hashing the names).
2. Probe. Before reading anything in full, the engine measures. Capped id probes find which substatements are small enough to enumerate exactly, and refinement waves let one selective leaf drive the rest of the query (Planning from Measured Cardinality) — this is what keeps a query like mod("amdgpu") { func { "drm_dev_enter" } } from resolving millions of rows it will immediately discard.
3. Read. Each command reads its rows under the layers now visible, conjoining its filter predicate.

Composition finishes the job. A monotone worklist propagates constraints between neighbouring substatements — a parent narrows its children, and each child narrows it back, so func { "a" ; "b" } keeps the callers of both — until nothing changes; the instances still standing, and the edges among them, are emitted as the result graph (Evaluating the Fixpoint).

Three questions link

Every part of that pipeline is there for a reason, and the reasons are answers to three questions that a graph-returning query language cannot avoid. Each one creates the next.

1. What does a query mean? Neighbouring parts of a query constrain each other, so no part can be evaluated on its own. The answer is a fixpoint (Queries and their Meaning).
2. How is it evaluated without being slow? The fixpoint has to be computed over an index of millions of rows, and syntax cannot predict how many rows a pattern will match — so the engine measures before it reads (Evaluating the Fixpoint, Planning from Measured Cardinality).
3. How is work reused across queries? An interactive session reruns near-identical queries, so the expensive parts must survive from one to the next. There are two kinds of work: what a command reads, and the rows it produces. Production becomes reusable once it is partitioned along the inputs it reads, and that partition is the chapter’s main contribution (Partitioning a Materialisation).

From Result to Cache is the single argument that runs through all three, from what a query returns down to why its results are stored the way they are; the pages after it develop one part each.

Terminology link

The pages share a vocabulary and a notation, both used with fixed meanings. This section is the reference for both; each term names the page that owns it.

Query structure.

• query — the whole parsed input: a sequence of statements.
• statement — one whole top-level unit of the query: a command, its scope, and everything nested under it. "foo" { "bar" } is one statement. Statements are the query’s only time axis; ; or a newline separates them. A @label may be referenced only from a later statement — same-statement and forward references are parse errors. Top-level statements are independent: their selections are unioned into the query’s nodes (derivation §2).
• substatement — any command-plus-scope node within a statement, at any depth. By convention a statement is a substatement of itself, so machinery that is uniform over nodes (weakness, probes, hashes) is stated once, per substatement. The engine’s Statement type corresponds to substatement.
• scope — the { } block of a substatement, holding its children. Sibling children conjoin: the parent survives only with evidence to each of them, so func { "a" ; "b" } keeps the callers of both, and an empty child empties the parent (semantics §7). Disjunction is spelled inside one command: func { "a" "b" } is a single child with two selector branches. At top level, ; separates statements.
• command — the verb bag of one substatement, assembled by folding its verbs in source order; a later verb may override an earlier same-tagged one (Queries and their Meaning). Filters, predicates, and cache hashes are per-command.
• verb — the generic execution unit inside a command: search(...), project(...), func(...). What a verb contributes varies — a filter, layer content, or both.
• filter — a constraint on rows that a command carries alongside its content verbs: project("linux"), a type constraint, ignore(...). A command’s filters are combined into a single predicate $F_c$, a tree of leaves under And/Or/Not nodes, and “the command’s filter” means that composite (Layer Keys §1).
• selector branch — a way into the index that a command offers: a name pattern ("foo", func("open")), a search match, a loc position. A command’s branches are OR-ed with one another and conjoined with its filters, and the result is its predicate $P(c)$ (semantics §6). Branches disjoin where filters conjoin, so which of the two slots a condition lands in decides whether adding it widens or narrows.
• component — one or more statements connected by label references; the unit of the anchor rule and of bindness.
• anchor — a verb that can produce instances on its own: a name pattern, a name filter, search(...), loc(...), a layer literal, or select. Every other verb narrows what an anchor produced, so a binding component without one has nothing to narrow and is rejected before the query runs (semantics §9.2).
• weakness — whether a command’s selection constrains its neighbours. A weak substatement is a display echo: it contributes nodes and edges, and its parent and children survive whether or not it matches (semantics §9.1). An anchored command is always strong (semantics §9.3).
• bindness — whether a component demands instances at all. A binding component wants results and must be satisfiable; a non-binding one is structure or directive, and is silently empty (semantics §9.2).

What a query means.

• denotation — $D(c)$, what command $c$’s own predicate $P(c)$ — its filters and its selector branches — picks out of the visible instances. It is computable from the command alone, before any neighbour has been consulted (semantics §6).
• selection — $N_c$, the instances a command holds once the worklist fixpoint has run, closed per symbol; $N_s$ for a whole statement, $N$ for the whole query (semantics §7). The referenced outputs $O_c$ of a command are earlier statements' selections. (The selection function $\sigma_{F_c}$ is relational-algebra notation for filtering a row set.)
• evidence relation — $\hat{E}_{c,n}$, the edge kind that the nesting between a command and a neighbour asks for, read as a relation between symbols and oriented from $c$ towards $n$; reversing the pair inverts it. It is what a row must have with a constraining neighbour’s selection in order to survive (semantics §7).
• populate — the function a content verb contributes: given a slice of layer content, it returns the rows that verb writes for just that slice (semantics §1). The engine fills a layer’s rows by running populates; $U_c$ is a command’s populates unioned.
• wave — one probe iteration of the cost-based executor: wave 0 plus the refinement waves, all within a single statement’s probe phase.
• probe — one capped question about a set of instances: are there at most $k$ of them, and if so which? It is an id fetch stopped after $k+1$ rows, so a single database statement answers both halves (planning §4).
• resolved, capped — a probe’s two outcomes. A resolved substatement holds the exact ids of what it probed and reuses them in place of that predicate; a capped one hit the cap, its fetched ids are discarded, and it stays predicate-driven. Only anchored substatements probe, so a resolved neighbour is always a strong one.
• role — the semi-join image of a resolved neighbour’s ids under one relationship, lifted to symbol level: what that neighbour can reach, conjoined into a substatement’s predicate to narrow it before it reads (planning §5). The worklist’s dependency roles — child, parent, user — are a separate use of the word: they name the direction a notification travels (evaluation §2.2).
• REFS, HAS — the two edge kinds a nesting can ask for: a REFS edge is a reference (one symbol calls or uses another), a HAS edge is containment (a module contains a function). A scope written { } with no relationship modifier asks for either; @has and @refs pin it. Which kind a nesting asks for is what its evidence relation stands for.

Storage and reuse.

• layer — a labelled set of graph rows: one index.layers row plus every object, symbol, instance, and reference tagged with its id. Every row belongs to exactly one layer, and a query sees a flat set of visible layer ids (Layers §2).
• root layer — $R$, a project’s initial persistent layer, carrying a stored identity hash $h(R)$ that names the committed index state it stands for. With any later persistent delta layers it forms the project’s persistent closure (Layers §3), which is the one page that writes it $R_p$, having to tell the initial layer from the deltas beside it.
• ephemeral layer — a layer materialised by a verb during a query, holding that command’s output. It lives in the same tables as the persistent index and is read by the same SQL; its lifetime is that of a cache entry, governed by TTL and LRU (Layers §3, Caching).
• materialisation — the set of layers one layer-creating statement produces on one project, appended to visibility atomically (push_materialisation). Statements and their materialisations correspond one-to-one, so $t$ indexes both.
• shard — a node holding one dependency’s part of a command’s materialisation, stored and keyed on its own. There are three kinds, derived in Partitioning a Materialisation §3; they are the engine’s ShardRole::Root, Layer, and Selection.
• root shard — $\mathrm{Sh}_c(R)$, the part of the materialisation the command’s populate produces from the root layer’s content: the expensive scan of the committed corpus. Its key names $h(R)$ and $H(c)$ and nothing about the query’s ephemeral context, so it is shared by every query that runs the same command against the same corpus.
• layer shard — $\mathrm{Sh}_c(\ell)$, the same populate over one content-bearing light layer — a visible non-root layer whose rows a populate reads, one of the set $E_t(R)$ — keyed by that layer’s id. Root and layer shards together are the input shards: the shards whose parent is the very input they read.
• selection shard — $S_c(R)$, the per-command node parented on the previous statement’s tip; it holds everything the command builds from earlier statements’ selections, and marks the chain position when empty. A statement’s selection-shard-bearing commands contribute sibling selection shards. The root is written only where several projects are in view, so Layer Keys — which works inside one — has it as $S_c$.
• tip — $\mathrm{tip}_t(R)$, the last layer of statement $t$’s materialisation in command pre-order: the layer the next statement’s selection shards hang off (Layers §5).
• spine — the chain of tips, one per statement — the only lineage in the layer forest that encodes query history (shards §5).
• command hash — $H(c)$, a canonical hash summarising a command, so that equal hashes mean semantically identical commands. It names every input the command’s populates read, up to but not including the layer content they are aimed at; the node keys name that (Layer Keys §4).

The pages, in reading order link

The chapter is written to be read in order — each page’s problem is created by the one before it — but every page opens by stating that problem, so it can also be entered directly. Read the first four for what a query means and how it is evaluated; the next four for how results are stored and reused, which is where the design is least obvious; the last for one verb end to end, in SQL and in milliseconds.

Evaluating a query

• From Result to Cache — the chapter in one argument: why the engine has the parts it has, derived from what a query returns.
• Queries and their Meaning — how a bag of verbs folds into one predicate and one populate, and why a query’s answer is a fixpoint of mutually constraining selections.
• Evaluating the Fixpoint — the phases a statement runs, the monotone worklist that composes neighbouring substatements, and why it terminates.
• Planning from Measured Cardinality — anchors, capped id probes, and the refinement waves that let one selective leaf drive a query.

Storing and reusing results

• Layers and layer operations — why intermediate results are rows at all, how a query decides what it can see, and the isolation guarantee.
• Partitioning a Materialisation — the contribution: production carved along its dependencies, so an expensive result survives a change to a volatile input.
• Layer Keys and Hashing — one rule at byte level: name what a populate reads, and nothing more.
• Caching — the two tiers, and the invariants that keep a cached answer from outliving the state it was computed from.

One verb in depth

• search() — turning a literal string into byte-range matches over the whole corpus, without regex and with byte-exact positions: the abstractions above cashed out against real SQL and real numbers. Its helper’s full body and the measurements behind its claims are in search(): Implementation Notes.