How should I handle recursive records when driving the Rust API?

[twitchyliquid64]

Consider this nickel:

let rec
  b1 = {
    name = "build 1",
    inputs = [b2],
  },
  b2 = {
    name = "build 2",
    inputs = [b1],
  },

in
b1

Note that b1 is listed as b2's input, and vice-versa, making this recursive.

I get into an infinite loop with growing memory as soon as I build a Program out of this and call eval_full_for_export(). This makes sense, given that method is for exporting to JSON or whatever.

My question is, how can I eval the RichTerm tree in a manner that doesn't explode when there are recursive definitions, and handle circular references like this myself?

Thanks,
Tom

[yannham]

Hello!

This is indeed something we have to account for in several places in the Nickel pipeline. It's fair that an export loops, as you mention. However, nickel doc must be able to handle those kind of cyclic structures (it happens in the wild that there are co-recursive default values, such as {foo | default = derive_from_bar bar, bar | default = derive_from_foo foo} so that you only have to set one). The second case that comes to mind is the background evaluator of the LSP (there's background evaluation to report contract errors live).

The general idea is to rely on the lazy evaluation strategy of Nickel. The default evaluation strategy for Nickel, if you're using eval_closure for example, is to stop as soon as it sees a data structure - here, the record b1 - without recursing inside. The fields are left unevaluated. eval_full_for_export() forces the result, but if you used b1.name instead as the last expression, that would work because inputs is never used and isn't part of the final result (including with eval_full_for_export).

So I would say it depends on what you want to do with the data, and how deep you want to explore the result.

The nickel doc way

As an example, nickel doc uses the lazy evaluation strategy to recurse step by step in a value in the following way:

• lazily evaluate the top-level expression to a literal, a data structure or a function
• if it's a record, recurse into each field:
  • evaluate (lazily) the content of the field. If there is an error, abort. If it's a record, rinse, repeat.
  • there's an additional locking mechanism to avoid infinite recursion, so that if we go through a field while we were evaluating said field to begin with, leave it unevaluated and proceed with its next sibling

The result is what we call the record spine. It's implemented by program::Program::eval_record_spine, with the real logic in the freestanding function maybe_closurized_eval_record_spine:

nickel/core/src/program.rs

Lines 918 to 1012 in aa76d8e

	fn maybe_closurized_eval_record_spine(&mut self, closurize: bool) -> Result<RichTerm, Error> {
	use crate::{
	eval::Environment,
	match_sharedterm,
	term::{record::RecordData, RuntimeContract},
	};
	let prepared = self.prepare_eval()?;
	// Naively evaluating some legit recursive structures might lead to an infinite loop. Take
	// for example this simple contract definition:
	//
	// ```nickel
	// {
	// Tree = {
	// data | Number,
	// left | Tree | optional,
	// right | Tree | optional,
	// }
	// }
	// ```
	//
	// Here, we don't want to unfold the occurrences of `Tree` appearing in `left` and `right`,
	// or we will just go on indefinitely (until a stack overflow in practice). To avoid this,
	// we store the cache index (thunk) corresponding to the content of the `Tree` field before
	// evaluating it. After we have successfully evaluated it to a record, we mark it (lock),
	// and if we come across the same thunk while evaluating one of its children, here `left`
	// for example, we don't evaluate it further.
	// Eval pending contracts as well, in order to extract more information from potential
	// record contract fields.
	fn eval_contracts<EC: EvalCache>(
	vm: &mut VirtualMachine<CacheHub, EC>,
	mut pending_contracts: Vec<RuntimeContract>,
	current_env: Environment,
	closurize: bool,
	) -> Result<Vec<RuntimeContract>, Error> {
	vm.reset();
	for ctr in pending_contracts.iter_mut() {
	let rt = ctr.contract.clone();
	// Note that contracts can't be referred to recursively, as they aren't binding
	// anything. Only fields are. This is why we pass `None` for `self_idx`: there is
	// no locking required here.
	ctr.contract = eval_guarded(vm, rt, current_env.clone(), closurize)?;
	}
	Ok(pending_contracts)
	}
	// Handles thunk locking (and unlocking upon errors) to detect infinite recursion, but
	// hands over the meat of the work to `do_eval`.
	fn eval_guarded<EC: EvalCache>(
	vm: &mut VirtualMachine<CacheHub, EC>,
	term: RichTerm,
	env: Environment,
	closurize: bool,
	) -> Result<RichTerm, Error> {
	vm.reset();
	let curr_thunk = term.as_ref().try_as_closure();
	if let Some(thunk) = curr_thunk.as_ref() {
	// If the thunk is already locked, it's the thunk of some parent field, and we stop
	// here to avoid infinite recursion.
	if !thunk.lock() {
	return Ok(term);
	}
	}
	let result = do_eval(vm, term.clone(), env, closurize);
	// Once we're done evaluating all the children, or if there was an error, we unlock the
	// current thunk
	if let Some(thunk) = curr_thunk.as_ref() {
	thunk.unlock();
	}
	// We expect to hit `MissingFieldDef` errors. When a configuration
	// contains undefined record fields they most likely will be used
	// recursively in the definition of some other fields. So instead of
	// bubbling up an evaluation error in this case we just leave fields
	// that depend on as yet undefined fields unevaluated; we wouldn't
	// be able to extract dcoumentation from their values anyways. All
	// other evaluation errors should however be reported to the user
	// instead of resulting in documentation being silently skipped.
	if matches!(
	result,
	Err(Error::EvalError(EvalError::MissingFieldDef { .. }))
	) {
	return Ok(term);
	}
	result
	}

One gotcha, if you were to re-use this function as it is, is that it doesn't bother recursing into other things than records (enum variants, arrays, etc.), because of the goal of nickel doc. But it could be rather easily adapted.

The NLS way

NLS (Nickel Language Server) uses a similar technique, but with a few differences:

• the recursive situation is a bit different here: we might unveil contract errors by unfolding some recursive definitions (they might still be productive). Instead of thread locking, NLS uses a simple recursion limit to avoid infinite loops.
• it does recurse into other forms, such as arrays and enum tags
• it doesn't abort on errors, but leaves the field unevaluated and proceed with its next sibling, in order to collect as many errors as possible.

The logic is implemented in eval_permissive:

nickel/core/src/eval/mod.rs

Lines 1017 to 1087 in aa76d8e

	/// Evaluate a term, but attempt to continue on errors.
	///
	/// This differs from `VirtualMachine::eval_full` in three ways:
	/// - We try to accumulate errors instead of bailing out. When recursing into record
	/// fields and array elements, we keep evaluating subsequent elements even if one
	/// fails.
	/// - We only return the accumulated errors; we don't return the eval'ed term.
	/// - We support a recursion limit, to limit the number of times we recurse into
	/// arrays or records.
	pub fn eval_permissive(&mut self, rt: RichTerm, recursion_limit: usize) -> Vec<EvalError> {
	fn inner<R: ImportResolver, C: Cache>(
	slf: &mut VirtualMachine<R, C>,
	acc: &mut Vec<EvalError>,
	rt: RichTerm,
	recursion_limit: usize,
	) {
	if recursion_limit == 0 {
	return;
	}
	let pos = rt.pos;
	match slf.eval(rt) {
	Err(e) => {
	acc.push(e);
	slf.reset();
	}
	Ok(t) => match t.as_ref() {
	Term::Array(ts, attrs) => {
	for t in ts.iter() {
	// After eval_closure, all the array elements are
	// closurized already, so we don't need to do any tracking
	// of the env.
	let value_with_ctr = RuntimeContract::apply_all(
	t.clone(),
	attrs.pending_contracts.iter().cloned(),
	t.pos,
	);
	inner(slf, acc, value_with_ctr, recursion_limit.saturating_sub(1));
	}
	}
	Term::Record(data) => {
	for (id, field) in &data.fields {
	if let Some(v) = &field.value {
	let value_with_ctr = RuntimeContract::apply_all(
	v.clone(),
	field.pending_contracts.iter().cloned(),
	v.pos,
	);
	inner(slf, acc, value_with_ctr, recursion_limit.saturating_sub(1));
	} else {
	acc.push(EvalError::MissingFieldDef {
	id: *id,
	metadata: field.metadata.clone(),
	pos_record: pos,
	pos_access: TermPos::None,
	});
	}
	}
	}
	Term::EnumVariant { arg, .. } => {
	inner(slf, acc, arg.clone(), recursion_limit.saturating_sub(1));
	}
	_ => {}
	},
	}
	}
	let mut ret = Vec::new();
	inner(self, &mut ret, rt, recursion_limit);
	ret
	}
	}

I suppose, mixing the two techniques (for example using the thread locking to avoid recursion altogether and just mark it for later processing, but descending into arrays and enum variants as opposed to nickel doc), that you can cover a wide range of usage.

One caveat is that this interleaving of the VM and an external function is less efficient that having the VM do all the work in one run, since it's a stack machine. Hard to tell if the penalty is significant, depending on the implementation of your eval_with_my_strategy, but I would bet it's at least measurable.

[twitchyliquid64]

Thank for for the detailed explanation! I'm working on applying this and will let you know how it goes!

[twitchyliquid64]

So I'm able to walk the RichTerm tree without it exploding by calling Program::eval_record_spine or Program::eval, then recursively walking the tree and resolving any closures as I hit them with Program::eval_closure. That works at least for the recursive walking piece, so thank you!

Two questions:

1. I'm calling Program::eval_closure at every level as its the only method that lets me evaluate an arbitrary closure. Would it be better if there was a eval_record_spine variant that took a closure, which would be better to implement and use instead?
2. I want to be able to detect when I'm recursing and hit an object that I've seen before. How can I test for equality for a Closure or RichTern? Ive tried matching thunk UIDs and calling ptr_eq to no avail, nothing seems to match despite comparing results for a RichTerm representing the same object. Looking at pos or RawSpan doesn't seem to work either if the value passes through functions.

On (2), perhaps its not possible to identify record declarations uniquely, in which case is it possible to have something like a field value which is a magic unique integer we can use as a deduplication key - perhaps implemented by walking the AST and writing in ForeignId values?

[yannham]

I'm calling Program::eval_closure at every level as its the only method that lets me evaluate an arbitrary closure. Would it be better if there was a eval_record_spine variant that took a closure, which would be better to implement and use instead?

Do you intend to call this hypothetical eval_record_spine_closure repeatedly, or just once to get the unevaluated spine? Or I guess, my more general question is, what kind of evaluation are you trying to perform here?

As to 2., I must first state that it's not always possible to detect loops. Beyond the fact that it's undecidable in general (you could still detect them conservatively though, accepting false positives), the technique used by Nickel, called thunk blackholing, only detects direct loops (that don't involve e.g. recursive function calls). Also, thunks are just a unit of allocation: it can very much be the case that the same expression, at the same location of a source, give rise to many different thunks at runtime because it's used in different contexts. Merging also interact with thunking in a non-trivial way.

That being said, using thunk IDs (that is, in practice, their pointer value as usize) should be sufficient for most basic co-recursive record fields. If you look at the code of eval_record_spine, it's using the lock() and unlock() functions on thunks, which stores the bit of information "have I ever seen this thread before, and locked it" directly alongside the thunk, so that we can detect such loops efficiently. But in the end, it's just an optimization. You should be able to detect the same loops by just storing seen thunk IDs somewhere in e.g. HashSet, or comparing them by value. Do you have an example of when you'd like to detect that two objects are the same, but it's not working currently?

[twitchyliquid64]

Do you intend to call this hypothetical eval_record_spine_closure repeatedly, or just once to get the unevaluated spine? Or I guess, my more general question is, what kind of evaluation are you trying to perform here?

I'll spend a moment to explain my use of Nickel and how we intend to use it in a larger system. Ultimately, we are using Nickel to declare a graph of objects which represent software (libraries, binaries etc) and how to build them, and where edges represent dependencies between objects (including possible cycles). This declaration looks something like this:

let
  libabc = {
    name = "libabc",
    inputs = [],
    source = { /* where to find the source */ },
    build_cmd = "make",
  } | Build,
  my_binary = {
    name = "my binary",
    inputs = [libabc],
  } | Build,

in
my_binary

This representation is evaluated, and we want to deserialize it into a graph datastructure in memory in Rust.

Similar vibes to Nix, but not nix at all.

The challenge with this representation is that it doesn't form a simple tree of declarations, like normal configuration files or kubernetes manifests or anything like that. If it was just a tree of records, eval_full_for_export + Serde::deserialize would be all we need.

Last week, I got things working by deserializing everything then deep hashing each record to identify unique builds. I could then build the edges of the graph from that.

Unfortunately, this approach does not work when there are cycles in the graph.

So to answer your question directly, we are trying to evaluate this tree (with loops) of nickel objects into a graph of deserialized objects, where edges may have loops.

As for thunk UIDs, I wasn't able to observe any shared thunk UIDs even with a very simple cycle with two objects, perhaps due to merging :/

The hack that I am using to get things working for now

Yesterday, I got a hacky approach working where I used Program::custom_transform to traverse the RichTerm tree, looking for records which were merged with | Build and inject a unique ID:

let mut traversal = |rt: RichTerm| -> Result<RichTerm, CacheError<()>> {
            if let Term::Annotated(annotation, inner) = rt.as_ref() {
                let is_build = annotation.contracts.iter().any(|lt| {
                    if let TypeF::Contract(c) = &lt.typ.typ {
                        if let Term::Var(v) = c.as_ref() {
                            v.label() == "Build"
                        } else {
                            false
                        }
                    } else {
                        false
                    }
                });

                if is_build {
                    record_data.fields.insert(
                        LocIdent::new("__magic_build_id"),
                        RichTerm::from(Term::ForeignId(id)).into(),
                    );
                }
            }

            Ok(rt)
        };

Deserialization was more difficult, as unlike Program::eval_full the RichTerm tree returned by eval or eval_record_spine still has tons of non-"effective WHNF" terms in it. To handle this, I had to check at each record and field if it was WHNF and call either Program::eval_closure on the closure or make one with Program::eval_closure(Closure::atomic_closure(rt.clone())). Its not clear to me if I am doing eval correctly.

[yannham]

As for thunk UIDs, I wasn't able to observe any shared thunk UIDs even with a very simple cycle with two objects, perhaps due to merging :/

Could you please provide this cycle? I'm trying to understand if this is a practical issue that we can fix, or if it's just not going to work in general.

Describing a graph in a structured language is a general problem which, IMHO, doesn't have a good solution currently (I mean, even outside of Nickel). Nix uses some kind of string ids to do that (in some sense, you would write inputs = ["libabc"] instead of inputs = [libabc]), which has the advantage of breaking the cycle in a trivial way, but also makes it entirely "dynamic" (you wouldn't be able to go to definition anymore, or perform any kind of simple exploration/transformation in pure Nickel, or static analysis telling you "this libabc doesn't exist"). Using actual identifiers referring to Nickel values instead is indeed compelling.

I wonder if you could maybe use both thunk IDs and RichTerm (seen as pointers, so technically SharedTerm)? The latter is maybe less subject to change; any "copy" without modification, although it could end in a different thunk, should share the same allocated SharedTerm. However, if you ever merge or perform any kind of mutation, of course this will lead to a new allocation unit, unfortunately.

Relatedly, we have been wanting a proper hash function on Nickel values for different use-cases, but I think this would be for fully evaluated object - I haven't thought yet of a hash function accommodating for cycles...

[yannham]

Ah, I forgot, but regarding the "hacky" way of associating identifiers programmatically before evaluation, maybe a ForeignValue would be more adapted. It's a type of value we added when one needs to e.g. inject secrets at run-time into a Nickel program. Those are basically u64 but opaque to the program; as IDs, they might have less risk of colliding with user-code/leaking in unexpected ways.

[twitchyliquid64]

Could you please provide this cycle? I'm trying to understand if this is a practical issue that we can fix, or if it's just not going to work in general.

I’ll get back to you with a concrete example, but it was basically the example in the initial issue with the only difference being each build has a contract applied with ‘| Build’

maybe a ForeignValue would be more adapted

If you are referring to ‘Term::ForeignID(u64)’ then yepp that’s what we are using!

Relatedly, we have been wanting a proper hash function on Nickel values for different use-cases, but I think this would be for fully evaluated object - I haven't thought yet of a hash function accommodating for cycles...

If you can associate records with a unique ID, you can solve this by the usual recursive hashing except stopping recursion whenever you hit an ID you’ve already seen in the recursion call stack.

[twitchyliquid64]

I hear you on the difficulty of having a graph in Nickel, without dropping to an identifier like a string. FWIW, annotating the nickel term tree with injected ids has been surprisingly robust so far!