nix-reflect

A parser and an evaluator for the Nix language, written in Nix. parser.parse turns a string of Nix into a tree of attribute sets that you can inspect and rewrite, and eval reduces that tree to a value, with scopes, lazy thunks and typed errors implemented in Nix itself.

Because the whole thing is ordinary Nix code, it runs wherever nix eval does, and a Nix program can use it to read, transform and run Nix source as data. It is a work in progress: the last section measures how much of the language it handles today.

parser.parse · eval

One expression, its tree and its value

parser.parse "let a = rec { x = 1 + 1; y = x + 1; }; in a.x + a.y"
The parse tree of one expression The tree that parser.parse returns for: let a = rec { x = 1 + 1; y = x + 1; }; in a.x + a.y. The root is a let-in node whose binding assigns a recursive attribute set to a, with x bound to 1 + 1 and y to x + 1; its body adds a.x and a.y, each an attribute selection. Every node is labelled the way the library prints it and, where it has children, carries the exact slice of source text it was parsed from. Edges are labelled with the field that holds the child, such as lhs, rhs, body or bindings[0]. let _ in _let a = rec { x = 1 + 1; y = x + 1; }; in a.x + a.y <_ = _>a = rec { x = 1 + 1; y = x + 1; }; `a` rec {_}rec { x = 1 + 1; y = x + 1; } <_ = _>x = 1 + 1; `x` <_ + _>1 + 1 ℤ 1 ℤ 1 <_ = _>y = x + 1; `y` <_ + _>x + 1 `x` ℤ 1 <_ + _>a.x + a.y <_ . _>a.x `a` <_._._>x `x` <_ . _>a.y `a` <_._._>y `y` bindings[0] lhs rhs bindings[0] lhs rhs lhs rhs bindings[1] lhs rhs lhs rhs body lhs lhs rhs path[0] rhs lhs rhs path[0]
The tree as the parser returns it. Node labels are the library's own; under each inner node is the exact source it was parsed from. Edges name the field that holds the child.
eval "let a = rec { x = 1 + 1; y = x + 1; }; in a.x + a.y"
5

parser.parse :: string → AST

Parsing

The parser is built from nix-parsec, a parser-combinator library written in Nix. There is one small parser per construct (integers, strings, paths, lists, attribute sets, lambdas, let, with and so on), alternatives are tried with choice, and binary operators are layered by precedence from * and / down to ||, so 1 + 2 * 3 groups the way Nix groups it.

Every parser is wrapped so that the node it produces records the offset and the text it matched. Parsing " 1 + 2" gives a binaryOp node whose source is:

"1   +   2"

A node is an attribute set: a nodeType, its fields (lhs, op, rhs; bindings and body; param; …), the source text in __src, and mapNode and fmap for producing changed copies. Nothing is hidden behind a function, so a tree can be printed, compared, walked or rebuilt with ordinary Nix. true, false and null are not literals: they parse as identifiers and are looked up in scope, as in Nix.

Node types the parser produces
literalsint float string stringPieces interpolation path anglePath
namesidentifier attrPath
datalist attrs assignment inherit
functionslambda simpleParam attrSetParam defaultParam application
controlletIn conditional with assert throw abort
operatorsunaryOp binaryOp

eval :: string | AST → value

Evaluating

The evaluator walks the tree with one function per node type (evalLetIn, evalWith, evalLambda, evalApplication, …). Each returns a computation in an evaluation monad that the library defines for itself, in its own words "roughly an ExceptT EvalError (StateT EvalState m) stack": a step can read and update the evaluation state, or stop with an error, and the plumbing between steps is written once. The library also implements a do notation for these computations, so evaluation functions read as a sequence of named steps rather than nested callbacks.

From text to a value How eval works. Source text is parsed by parser combinators into an AST of attribute sets. evalM walks the AST, dispatching on each node's type, inside an evaluation monad: a computation that threads an EvalState (the scope of names in reach, a cache of thunks and their forced values, and a stack used for traces) and can stop with a typed EvalError. eval.either returns Right value or Left error; eval returns the value or throws the error. source text"1 + 2" parser.parsenix-parsec combinators ASTnodeType · fields · __src evalMdispatch on nodeType Right 3eval returns 3 Left EvalErrorThrow · TypeError · … scopenames in reach thunk cacheforced values stackfor traces EVALSTATE or stops threads
One computation, threaded state. Names in scope, the thunk cache and the call stack travel through every step; an error is a value, not a crash.

Laziness

Nix only evaluates what a result needs, so the evaluator does too. A binding becomes a thunk: the AST node, the scope at the point it was created, and an ID. Forcing a thunk looks it up in the cache held in the evaluation state; the first force evaluates it and stores the value, later ones reuse it. Because Nix values are immutable, "storing" means returning a new state, which the monad passes on.

eval evaluates as far as the outermost value (weak head normal form), as Nix does; eval.strict forces everything, which is what printing a whole list or attribute set needs.

Errors

eval.either returns Right value or Left error, where the error is one of a fixed set of kinds: Throw, Abort, AssertError, TypeError, UnknownIdentifierError, MissingAttributeError and a few internal ones. eval returns the value, or throws the error. A missing attribute under or is caught, so { a = 1; }.b or 42 is 42.

eval.either "1 + \"a\""
Left EvalError.TypeError:
  Incorrect types for binary operator +:
          1 and "a"
            (expected one of [ [ "int" "float" ] [ "string" "path" ] ])

mapNode · eval.eval.store

Code as data

Because a parsed expression is plain data, it can be rewritten before it is run. This swaps the operands of 1 + 2 and turns the + into a -, giving 2 - 1:

let
  ast = parser.parse "1 + 2";
  swapped = ast.mapNode (n: n // {
    op = "-"; lhs = n.rhs; rhs = n.lhs;
  });
in eval swapped
1

There is also a second, much simpler evaluator. eval.eval.store writes the text into the Nix store with a derivation and imports the result, so the real Nix evaluator does the work. It is fast and exact, but it needs import-from-derivation, and it offers none of the inspection the AST evaluator does.

eval.eval.store "1 + 1"
2

measured

How far it gets

Each expression below was evaluated twice, by the real Nix evaluator and by nix-reflect, by a script in the repository (scripts/site/capture.py). nix-reflect results are fully forced unless marked lazy. Times are for the whole nix eval run (about half a second of each is starting Nix), measured on a busy shared machine, so read them as orders of magnitude.

21 of 32 agree with Nix. Of the rest, 5 do not parse, and 6 parse but evaluate differently.

The same expressions, evaluated by Nix and by nix-reflect
ExpressionNixnix-reflectTime
arithmetic
1 + 2 * 37✓ 71.0 s
7 / 23✓ 30.7 s
1.5 * 23✓ 30.6 s
strings
let name = "nix"; in "hello ${name}""hello nix"✗ internal error0.8 s
'' indented block ''"indented\n block\n"✗ "\n indented\n block\n"0.5 s
"a" + "b" + toString 3"ab3"✗ UnknownIdentifierError0.9 s
lists
[ 1 2 ] ++ [ 3 ][ 1 2 3 ]✓ [ 1 2 3 ]1.1 s
builtins.map (x: x * 2) [ 1 2 3 ][ 2 4 6 ]✗ fails while evaluating1.2 s
builtins.foldl' (a: b: a + b) 0 [ 1 2 3 4 ]10✗ does not parse0.4 s
attrsets
let a = rec { x = 1 + 1; y = x + 1; }; in a.x + a.y5✓ 52.0 s
{ a = 1; } // { b = 2; }{ a = 1; b = 2; }✓ { a = 1; b = 2; }0.9 s
let x = 1; in { inherit x; y = 2; }{ x = 1; y = 2; }✓ { x = 1; y = 2; }0.9 s
{ a.b.c = 1; }{ a = { b = { c = 1; }; }; }✗ does not parse0.5 s
{ a = 1; }.b or 4242✓ 420.8 s
builtins.attrNames { b = 1; a = 2; }[ "a" "b" ]✓ [ "a" "b" ]1.0 s
functions
({ a, b ? 10, ... }: a + b) { a = 1; c = 3; }11✓ 111.1 s
(x: y: x - y) 10 37✓ 71.1 s
let f = args@{ a, ... }: args.b; in f { a = 1; b = 2; }2✗ does not parse0.4 s
control
if 1 < 2 then "yes" else "no""yes"✓ "yes"0.7 s
let x = { y = 1; }; in with x; y + 12✓ 21.1 s
assert 1 == 1; "ok""ok"✓ "ok"0.7 s
operators
{ a = 1; } ? atrue✗ does not parse0.4 s
true -> falsefalse✗ does not parse0.4 s
!(1 == 2) && truetrue✓ true0.8 s
laziness
let xs = [ 1 (throw "boom") 3 ]; in builtins.elemAt xs 23✗ Throwlazy 1.3 s
{ a = 1; b = throw "boom"; }.a1✓ 1lazy 0.8 s
let x = throw "boom"; in 11✓ 1lazy 0.7 s
recursion
let fib = n: if n < 2 then n else fib (n - 1) + fib (n - 2); in fib 55✓ 5lazy 14.4 s
let fib = n: if n < 2 then n else fib (n - 1) + fib (n - 2); in fib 713✓ 13lazy 43.6 s
let fib = n: if n < 2 then n else fib (n - 1) + fib (n - 2); in fib 1055✗ stack overflowlazy 8.6 s
errors
let x = 1; in yerror✓ both refuse0.6 s
1 + "a"error✓ both refuse0.6 s

What is missing

  • Syntax: the ? and -> operators, args@{ … } patterns, nested paths in bindings (a.b.c = 1) and identifiers containing ', such as foldl', do not parse yet.
  • Evaluation: string interpolation fails inside the evaluator; builtins such as map cannot yet call a function defined in the evaluated code; and list elements are evaluated eagerly, so one throw in a list fails the whole list where Nix would not care.
  • Functions from text: eval.fn, which builds a callable function from text and can rewrite its text or AST, fails on the current main branch: it expects eval to return an Either, and eval now returns the bare value.

Speed

Interpreting Nix in Nix is slow. Every step of the evaluated program is several monadic binds, each building new attribute sets for the state, inside an evaluator that is itself interpreted. A naive fib 7 takes most of a minute (the table has the measured time), and deep recursion exhausts the host evaluator's stack: fib 10 fails with a stack overflow even with Nix's call-depth limit raised.

That is fine for what the library is for, reflection over small expressions and configuration, and it is the obvious place for future work: a cheaper state representation or fewer binds per node.

flake

Using it

Add the flake as an input and use its lib output:

inputs.nix-reflect.url = "github:harryaskham/nix-reflect";

# in your outputs
with inputs.nix-reflect.lib.${system};
eval "let x = 2; in x * 21"   # 42

Or try it from a shell. Raise Nix's call-depth limit; the evaluator recurses deeply.

nix eval --option max-call-depth 1000000 \
    --apply 'lib: lib.eval "let x = 2; in x * 21"' \
    github:harryaskham/nix-reflect#lib.x86_64-linux
42

In a checkout, direnv provides run-tests (all suites, or one, such as run-tests eval.ast) and with-lib for evaluating against the library.