about summary refs log tree commit diff
path: root/tvix/nix-compat/src
diff options
context:
space:
mode:
Diffstat (limited to 'tvix/nix-compat/src')
-rw-r--r--tvix/nix-compat/src/derivation/errors.rs59
-rw-r--r--tvix/nix-compat/src/derivation/mod.rs240
-rw-r--r--tvix/nix-compat/src/derivation/output.rs36
-rw-r--r--tvix/nix-compat/src/derivation/string_escape.rs17
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv.json23
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv.json19
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv.json23
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv.json19
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv.json16
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv.json23
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv.json23
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv1
-rw-r--r--tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv.json23
-rw-r--r--tvix/nix-compat/src/derivation/tests/mod.rs315
-rw-r--r--tvix/nix-compat/src/derivation/validate.rs129
-rw-r--r--tvix/nix-compat/src/derivation/write.rs190
-rw-r--r--tvix/nix-compat/src/lib.rs5
-rw-r--r--tvix/nix-compat/src/nar/mod.rs1
-rw-r--r--tvix/nix-compat/src/nar/writer/mod.rs219
-rw-r--r--tvix/nix-compat/src/nar/writer/wire.rs46
-rw-r--r--tvix/nix-compat/src/nixbase32.rs167
-rw-r--r--tvix/nix-compat/src/nixhash/algos.rs39
-rw-r--r--tvix/nix-compat/src/nixhash/mod.rs454
-rw-r--r--tvix/nix-compat/src/nixhash/with_mode.rs136
-rw-r--r--tvix/nix-compat/src/store_path/mod.rs294
-rw-r--r--tvix/nix-compat/src/store_path/utils.rs289
33 files changed, 2813 insertions, 0 deletions
diff --git a/tvix/nix-compat/src/derivation/errors.rs b/tvix/nix-compat/src/derivation/errors.rs
new file mode 100644
index 000000000000..8e9e6a121096
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/errors.rs
@@ -0,0 +1,59 @@
+use crate::{nixbase32::Nixbase32DecodeError, store_path};
+use thiserror::Error;
+
+/// Errors that can occur during the validation of Derivation structs.
+#[derive(Debug, Error, PartialEq)]
+pub enum DerivationError {
+    // outputs
+    #[error("no outputs defined")]
+    NoOutputs(),
+    #[error("invalid output name: {0}")]
+    InvalidOutputName(String),
+    #[error("encountered fixed-output derivation, but more than 1 output in total")]
+    MoreThanOneOutputButFixed(),
+    #[error("invalid output name for fixed-output derivation: {0}")]
+    InvalidOutputNameForFixed(String),
+    #[error("unable to validate output {0}: {1}")]
+    InvalidOutput(String, OutputError),
+    #[error("unable to validate output {0}: {1}")]
+    InvalidOutputDerivationPath(String, store_path::BuildStorePathError),
+    // input derivation
+    #[error("unable to parse input derivation path {0}: {1}")]
+    InvalidInputDerivationPath(String, store_path::Error),
+    #[error("input derivation {0} doesn't end with .drv")]
+    InvalidInputDerivationPrefix(String),
+    #[error("input derivation {0} output names are empty")]
+    EmptyInputDerivationOutputNames(String),
+    #[error("input derivation {0} output name {1} is invalid")]
+    InvalidInputDerivationOutputName(String, String),
+
+    // input sources
+    #[error("unable to parse input sources path {0}: {1}")]
+    InvalidInputSourcesPath(String, store_path::Error),
+
+    // platform
+    #[error("invalid platform field: {0}")]
+    InvalidPlatform(String),
+
+    // builder
+    #[error("invalid builder field: {0}")]
+    InvalidBuilder(String),
+
+    // environment
+    #[error("invalid environment key {0}")]
+    InvalidEnvironmentKey(String),
+}
+
+/// Errors that can occur during the validation of a specific
+// [crate::derivation::Output] of a [crate::derivation::Derviation].
+#[derive(Debug, Error, PartialEq)]
+pub enum OutputError {
+    #[error("Invalid output path {0}: {1}")]
+    InvalidOutputPath(String, store_path::Error),
+    #[error("Invalid hash encoding: {0}")]
+    InvalidHashEncoding(String, Nixbase32DecodeError),
+    #[error("Invalid hash algo: {0}")]
+    InvalidHashAlgo(String),
+    #[error("Invalid Digest size {0} for algo {1}")]
+    InvalidDigestSizeForAlgo(usize, String),
+}
diff --git a/tvix/nix-compat/src/derivation/mod.rs b/tvix/nix-compat/src/derivation/mod.rs
new file mode 100644
index 000000000000..ab1471165549
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/mod.rs
@@ -0,0 +1,240 @@
+use crate::store_path::{
+    self, build_output_path, build_regular_ca_path, build_text_path, StorePath,
+};
+use serde::{Deserialize, Serialize};
+use sha2::{Digest, Sha256};
+use std::collections::{BTreeMap, BTreeSet};
+
+mod errors;
+mod output;
+mod string_escape;
+mod validate;
+mod write;
+
+#[cfg(test)]
+mod tests;
+
+// Public API of the crate.
+pub use crate::nixhash::{NixHash, NixHashWithMode};
+pub use errors::{DerivationError, OutputError};
+pub use output::Output;
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)]
+pub struct Derivation {
+    #[serde(rename = "args")]
+    pub arguments: Vec<String>,
+
+    pub builder: String,
+
+    #[serde(rename = "env")]
+    pub environment: BTreeMap<String, String>,
+
+    #[serde(rename = "inputDrvs")]
+    pub input_derivations: BTreeMap<String, BTreeSet<String>>,
+
+    #[serde(rename = "inputSrcs")]
+    pub input_sources: BTreeSet<String>,
+
+    pub outputs: BTreeMap<String, Output>,
+
+    pub system: String,
+}
+
+impl Derivation {
+    /// write the Derivation to the given [std::fmt::Write], in ATerm format.
+    ///
+    /// The only errors returns are these when writing to the passed writer.
+    pub fn serialize(&self, writer: &mut impl std::fmt::Write) -> Result<(), std::fmt::Error> {
+        writer.write_str(write::DERIVATION_PREFIX)?;
+        writer.write_char(write::PAREN_OPEN)?;
+
+        write::write_outputs(writer, &self.outputs)?;
+        write::write_input_derivations(writer, &self.input_derivations)?;
+        write::write_input_sources(writer, &self.input_sources)?;
+        write::write_system(writer, &self.system)?;
+        write::write_builder(writer, &self.builder)?;
+        write::write_arguments(writer, &self.arguments)?;
+        write::write_enviroment(writer, &self.environment)?;
+
+        writer.write_char(write::PAREN_CLOSE)?;
+
+        Ok(())
+    }
+
+    /// return the ATerm serialization as a string.
+    pub fn to_aterm_string(&self) -> String {
+        let mut buffer = String::new();
+
+        // invoke serialize and write to the buffer.
+        // Note we only propagate errors writing to the writer in serialize,
+        // which won't panic for the string we write to.
+        self.serialize(&mut buffer).unwrap();
+
+        buffer
+    }
+
+    /// Returns the drv path of a [Derivation] struct.
+    ///
+    /// The drv path is calculated by invoking [build_text_path], using
+    /// the `name` with a `.drv` suffix as name, all [Derivation::input_sources] and
+    /// keys of [Derivation::input_derivations] as references, and the ATerm string of
+    /// the [Derivation] as content.
+    pub fn calculate_derivation_path(&self, name: &str) -> Result<StorePath, DerivationError> {
+        // append .drv to the name
+        let name = &format!("{}.drv", name);
+
+        // collect the list of paths from input_sources and input_derivations
+        // into a (sorted, guaranteed by BTreeSet) list of references
+        let references: BTreeSet<String> = {
+            let mut inputs = self.input_sources.clone();
+            let input_derivation_keys: Vec<String> =
+                self.input_derivations.keys().cloned().collect();
+            inputs.extend(input_derivation_keys);
+            inputs
+        };
+
+        build_text_path(name, self.to_aterm_string(), references)
+            .map_err(|_e| DerivationError::InvalidOutputName(name.to_string()))
+    }
+
+    /// Returns the FOD digest, if the derivation is fixed-output, or None if
+    /// it's not.
+    fn fod_digest(&self) -> Option<Vec<u8>> {
+        if self.outputs.len() != 1 {
+            return None;
+        }
+
+        let out_output = self.outputs.get("out")?;
+        Some(
+            Sha256::new_with_prefix(format!(
+                "fixed:out:{}:{}",
+                out_output.hash_with_mode.clone()?.to_nix_hash_string(),
+                out_output.path
+            ))
+            .finalize()
+            .to_vec(),
+        )
+    }
+
+    /// Calculates the hash of a derivation modulo fixed-output subderivations.
+    ///
+    /// This is called `hashDerivationModulo` in nixcpp.
+    ///
+    /// It returns a [NixHash], created by calculating the sha256 digest of
+    /// the derivation ATerm representation, except that:
+    ///  -  any input derivation paths have beed replaced "by the result of a
+    ///     recursive call to this function" and that
+    ///  - for fixed-output derivations the special
+    ///    `fixed:out:${algo}:${digest}:${fodPath}` string is hashed instead of
+    ///    the A-Term.
+    ///
+    /// If the derivation is not a fixed derivation, it's up to the caller of
+    /// this function to provide a lookup function to lookup these calculation
+    /// results of parent derivations at `fn_get_hash_derivation_modulo` (by
+    /// drv path).
+    pub fn derivation_or_fod_hash<F>(&self, fn_get_derivation_or_fod_hash: F) -> NixHash
+    where
+        F: Fn(&str) -> NixHash,
+    {
+        // Fixed-output derivations return a fixed hash.
+        // Non-Fixed-output derivations return a hash of the ATerm notation, but with all
+        // input_derivation paths replaced by a recursive call to this function.
+        // We use fn_get_derivation_or_fod_hash here, so callers can precompute this.
+        let digest = self.fod_digest().unwrap_or({
+            // This is a new map from derivation_or_fod_hash.digest (as lowerhex)
+            // to list of output names
+            let mut replaced_input_derivations: BTreeMap<String, BTreeSet<String>> =
+                BTreeMap::new();
+
+            // For each input_derivation, look up the
+            // derivation_or_fod_hash, and replace the derivation path with it's HEXLOWER
+            // digest.
+            // This is not the [NixHash::to_nix_hash_string], but without the sha256: prefix).
+            for (drv_path, output_names) in &self.input_derivations {
+                replaced_input_derivations.insert(
+                    data_encoding::HEXLOWER.encode(&fn_get_derivation_or_fod_hash(drv_path).digest),
+                    output_names.clone(),
+                );
+            }
+
+            // construct a new derivation struct with these replaced input derivation strings
+            let replaced_derivation = Derivation {
+                input_derivations: replaced_input_derivations,
+                ..self.clone()
+            };
+
+            // write the ATerm of that to the hash function
+            let mut hasher = Sha256::new();
+            hasher.update(replaced_derivation.to_aterm_string());
+
+            hasher.finalize().to_vec()
+        });
+        NixHash::new(crate::nixhash::HashAlgo::Sha256, digest.to_vec())
+    }
+
+    /// This calculates all output paths of a Derivation and updates the struct.
+    /// It requires the struct to be initially without output paths.
+    /// This means, self.outputs[$outputName].path needs to be an empty string,
+    /// and self.environment[$outputName] needs to be an empty string.
+    ///
+    /// Output path calculation requires knowledge of the
+    /// derivation_or_fod_hash [NixHash], which (in case of non-fixed-output
+    /// derivations) also requires knowledge of other hash_derivation_modulo
+    /// [NixHash]es.
+    ///
+    /// We solve this by asking the caller of this function to provide the
+    /// hash_derivation_modulo of the current Derivation.
+    ///
+    /// On completion, self.environment[$outputName] and
+    /// self.outputs[$outputName].path are set to the calculated output path for all
+    /// outputs.
+    pub fn calculate_output_paths(
+        &mut self,
+        name: &str,
+        derivation_or_fod_hash: &NixHash,
+    ) -> Result<(), DerivationError> {
+        // The fingerprint and hash differs per output
+        for (output_name, output) in self.outputs.iter_mut() {
+            // Assert that outputs are not yet populated, to avoid using this function wrongly.
+            // We don't also go over self.environment, but it's a sufficient
+            // footgun prevention mechanism.
+            assert!(output.path.is_empty());
+
+            let path_name = output_path_name(name, output_name);
+
+            // For fixed output derivation we use the per-output info, otherwise we use the
+            // derivation hash.
+            let abs_store_path = if let Some(ref hwm) = output.hash_with_mode {
+                build_regular_ca_path(&path_name, hwm, Vec::<String>::new(), false).map_err(
+                    |e| DerivationError::InvalidOutputDerivationPath(output_name.to_string(), e),
+                )?
+            } else {
+                build_output_path(derivation_or_fod_hash, output_name, &path_name).map_err(|e| {
+                    DerivationError::InvalidOutputDerivationPath(
+                        output_name.to_string(),
+                        store_path::BuildStorePathError::InvalidName(e),
+                    )
+                })?
+            };
+
+            output.path = abs_store_path.to_absolute_path();
+            self.environment
+                .insert(output_name.to_string(), abs_store_path.to_absolute_path());
+        }
+
+        Ok(())
+    }
+}
+
+/// Calculate the name part of the store path of a derivation [Output].
+///
+/// It's the name, and (if it's the non-out output), the output name
+/// after a `-`.
+fn output_path_name(derivation_name: &str, output_name: &str) -> String {
+    let mut output_path_name = derivation_name.to_string();
+    if output_name != "out" {
+        output_path_name.push('-');
+        output_path_name.push_str(output_name);
+    }
+    output_path_name
+}
diff --git a/tvix/nix-compat/src/derivation/output.rs b/tvix/nix-compat/src/derivation/output.rs
new file mode 100644
index 000000000000..4bfc7bf8014d
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/output.rs
@@ -0,0 +1,36 @@
+use crate::derivation::OutputError;
+use crate::nixhash::{HashAlgo, NixHashWithMode};
+use crate::store_path::StorePath;
+use serde::{Deserialize, Serialize};
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)]
+pub struct Output {
+    pub path: String,
+
+    #[serde(flatten)]
+    pub hash_with_mode: Option<NixHashWithMode>,
+}
+
+impl Output {
+    pub fn is_fixed(&self) -> bool {
+        self.hash_with_mode.is_some()
+    }
+
+    pub fn validate(&self, validate_output_paths: bool) -> Result<(), OutputError> {
+        if let Some(hash) = &self.hash_with_mode {
+            match hash {
+                NixHashWithMode::Flat(h) | NixHashWithMode::Recursive(h) => {
+                    if h.algo != HashAlgo::Sha1 || h.algo != HashAlgo::Sha256 {
+                        return Err(OutputError::InvalidHashAlgo(h.algo.to_string()));
+                    }
+                }
+            }
+        }
+        if validate_output_paths {
+            if let Err(e) = StorePath::from_absolute_path(&self.path) {
+                return Err(OutputError::InvalidOutputPath(self.path.to_string(), e));
+            }
+        }
+        Ok(())
+    }
+}
diff --git a/tvix/nix-compat/src/derivation/string_escape.rs b/tvix/nix-compat/src/derivation/string_escape.rs
new file mode 100644
index 000000000000..0e1dbe516f73
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/string_escape.rs
@@ -0,0 +1,17 @@
+const STRING_ESCAPER: [(char, &str); 5] = [
+    ('\\', "\\\\"),
+    ('\n', "\\n"),
+    ('\r', "\\r"),
+    ('\t', "\\t"),
+    ('\"', "\\\""),
+];
+
+pub fn escape_string(s: &str) -> String {
+    let mut s_replaced = s.to_string();
+
+    for escape_sequence in STRING_ESCAPER {
+        s_replaced = s_replaced.replace(escape_sequence.0, escape_sequence.1);
+    }
+
+    format!("\"{}\"", s_replaced)
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv
new file mode 100644
index 000000000000..a4fea3c5f486
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar","r:sha256","08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba")],[],[],":",":",[],[("builder",":"),("name","bar"),("out","/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar"),("outputHash","08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba"),("outputHashAlgo","sha256"),("outputHashMode","recursive"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv.json
new file mode 100644
index 000000000000..c8bbc4cbb5be
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv.json
@@ -0,0 +1,23 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "builder": ":",
+    "name": "bar",
+    "out": "/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar",
+    "outputHash": "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba",
+    "outputHashAlgo": "sha256",
+    "outputHashMode": "recursive",
+    "system": ":"
+  },
+  "inputDrvs": {},
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "hash": "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba",
+      "hashAlgo": "r:sha256",
+      "path": "/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv
new file mode 100644
index 000000000000..f0d9230a5a52
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/pzr7lsd3q9pqsnb42r9b23jc5sh8irvn-nested-json","","")],[],[],":",":",[],[("builder",":"),("json","{\"hello\":\"moto\\n\"}"),("name","nested-json"),("out","/nix/store/pzr7lsd3q9pqsnb42r9b23jc5sh8irvn-nested-json"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv.json
new file mode 100644
index 000000000000..9cb0b43b4c09
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/292w8yzv5nn7nhdpxcs8b7vby2p27s09-nested-json.drv.json
@@ -0,0 +1,19 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "builder": ":",
+    "json": "{\"hello\":\"moto\\n\"}",
+    "name": "nested-json",
+    "out": "/nix/store/pzr7lsd3q9pqsnb42r9b23jc5sh8irvn-nested-json",
+    "system": ":"
+  },
+  "inputDrvs": {},
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "path": "/nix/store/pzr7lsd3q9pqsnb42r9b23jc5sh8irvn-nested-json"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv
new file mode 100644
index 000000000000..a2cf9d31f92e
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/5vyvcwah9l9kf07d52rcgdk70g2f4y13-foo","","")],[("/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv",["out"])],[],":",":",[],[("bar","/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar"),("builder",":"),("name","foo"),("out","/nix/store/5vyvcwah9l9kf07d52rcgdk70g2f4y13-foo"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv.json
new file mode 100644
index 000000000000..957a85ccab82
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv.json
@@ -0,0 +1,23 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "bar": "/nix/store/4q0pg5zpfmznxscq3avycvf9xdvx50n3-bar",
+    "builder": ":",
+    "name": "foo",
+    "out": "/nix/store/5vyvcwah9l9kf07d52rcgdk70g2f4y13-foo",
+    "system": ":"
+  },
+  "inputDrvs": {
+    "/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv": [
+      "out"
+    ]
+  },
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "path": "/nix/store/5vyvcwah9l9kf07d52rcgdk70g2f4y13-foo"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv
new file mode 100644
index 000000000000..bbe88c02c739
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/vgvdj6nf7s8kvfbl2skbpwz9kc7xjazc-unicode","","")],[],[],":",":",[],[("builder",":"),("letters","räksmörgås\nrødgrød med fløde\nLübeck\n肥猪\nこんにちは / 今日は\n🌮\n"),("name","unicode"),("out","/nix/store/vgvdj6nf7s8kvfbl2skbpwz9kc7xjazc-unicode"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv.json
new file mode 100644
index 000000000000..f8f33c1bba17
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv.json
@@ -0,0 +1,19 @@
+{
+  "outputs": {
+    "out": {
+      "path": "/nix/store/vgvdj6nf7s8kvfbl2skbpwz9kc7xjazc-unicode"
+    }
+  },
+  "inputSrcs": [],
+  "inputDrvs": {},
+  "system": ":",
+  "builder": ":",
+  "args": [],
+  "env": {
+    "builder": ":",
+    "letters": "räksmörgås\nrødgrød med fløde\nLübeck\n肥猪\nこんにちは / 今日は\n🌮\n",
+    "name": "unicode",
+    "out": "/nix/store/vgvdj6nf7s8kvfbl2skbpwz9kc7xjazc-unicode",
+    "system": ":"
+  }
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv
new file mode 100644
index 000000000000..4b9338c0b953
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/6a39dl014j57bqka7qx25k0vb20vkqm6-structured-attrs","","")],[],[],":",":",[],[("__json","{\"builder\":\":\",\"name\":\"structured-attrs\",\"system\":\":\"}"),("out","/nix/store/6a39dl014j57bqka7qx25k0vb20vkqm6-structured-attrs")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv.json
new file mode 100644
index 000000000000..74e3d7df55c5
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv.json
@@ -0,0 +1,16 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "__json": "{\"builder\":\":\",\"name\":\"structured-attrs\",\"system\":\":\"}",
+    "out": "/nix/store/6a39dl014j57bqka7qx25k0vb20vkqm6-structured-attrs"
+  },
+  "inputDrvs": {},
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "path": "/nix/store/6a39dl014j57bqka7qx25k0vb20vkqm6-structured-attrs"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv
new file mode 100644
index 000000000000..1699c2a75e48
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/fhaj6gmwns62s6ypkcldbaj2ybvkhx3p-foo","","")],[("/nix/store/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv",["out"])],[],":",":",[],[("bar","/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar"),("builder",":"),("name","foo"),("out","/nix/store/fhaj6gmwns62s6ypkcldbaj2ybvkhx3p-foo"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv.json
new file mode 100644
index 000000000000..831d27956d86
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv.json
@@ -0,0 +1,23 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "bar": "/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar",
+    "builder": ":",
+    "name": "foo",
+    "out": "/nix/store/fhaj6gmwns62s6ypkcldbaj2ybvkhx3p-foo",
+    "system": ":"
+  },
+  "inputDrvs": {
+    "/nix/store/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv": [
+      "out"
+    ]
+  },
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "path": "/nix/store/fhaj6gmwns62s6ypkcldbaj2ybvkhx3p-foo"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv
new file mode 100644
index 000000000000..523612238c76
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv
@@ -0,0 +1 @@
+Derive([("lib","/nix/store/2vixb94v0hy2xc6p7mbnxxcyc095yyia-has-multi-out-lib","",""),("out","/nix/store/55lwldka5nyxa08wnvlizyqw02ihy8ic-has-multi-out","","")],[],[],":",":",[],[("builder",":"),("lib","/nix/store/2vixb94v0hy2xc6p7mbnxxcyc095yyia-has-multi-out-lib"),("name","has-multi-out"),("out","/nix/store/55lwldka5nyxa08wnvlizyqw02ihy8ic-has-multi-out"),("outputs","out lib"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv.json
new file mode 100644
index 000000000000..0bd7a2991cc7
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv.json
@@ -0,0 +1,23 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "builder": ":",
+    "lib": "/nix/store/2vixb94v0hy2xc6p7mbnxxcyc095yyia-has-multi-out-lib",
+    "name": "has-multi-out",
+    "out": "/nix/store/55lwldka5nyxa08wnvlizyqw02ihy8ic-has-multi-out",
+    "outputs": "out lib",
+    "system": ":"
+  },
+  "inputDrvs": {},
+  "inputSrcs": [],
+  "outputs": {
+    "lib": {
+      "path": "/nix/store/2vixb94v0hy2xc6p7mbnxxcyc095yyia-has-multi-out-lib"
+    },
+    "out": {
+      "path": "/nix/store/55lwldka5nyxa08wnvlizyqw02ihy8ic-has-multi-out"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv b/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv
new file mode 100644
index 000000000000..559e93ed0ed6
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv
@@ -0,0 +1 @@
+Derive([("out","/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar","r:sha1","0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33")],[],[],":",":",[],[("builder",":"),("name","bar"),("out","/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar"),("outputHash","0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"),("outputHashAlgo","sha1"),("outputHashMode","recursive"),("system",":")])
\ No newline at end of file
diff --git a/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv.json b/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv.json
new file mode 100644
index 000000000000..e297d271592f
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/derivation_tests/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv.json
@@ -0,0 +1,23 @@
+{
+  "args": [],
+  "builder": ":",
+  "env": {
+    "builder": ":",
+    "name": "bar",
+    "out": "/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar",
+    "outputHash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33",
+    "outputHashAlgo": "sha1",
+    "outputHashMode": "recursive",
+    "system": ":"
+  },
+  "inputDrvs": {},
+  "inputSrcs": [],
+  "outputs": {
+    "out": {
+      "hash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33",
+      "hashAlgo": "r:sha1",
+      "path": "/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar"
+    }
+  },
+  "system": ":"
+}
diff --git a/tvix/nix-compat/src/derivation/tests/mod.rs b/tvix/nix-compat/src/derivation/tests/mod.rs
new file mode 100644
index 000000000000..5daa16da03cb
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/mod.rs
@@ -0,0 +1,315 @@
+use crate::derivation::output::Output;
+use crate::derivation::Derivation;
+use crate::nixhash::NixHash;
+use crate::store_path::StorePath;
+use std::collections::BTreeSet;
+use std::fs::File;
+use std::io::Read;
+use std::path::Path;
+use test_case::test_case;
+use test_generator::test_resources;
+
+const RESOURCES_PATHS: &str = "src/derivation/tests/derivation_tests";
+
+fn read_file(path: &str) -> String {
+    let path = Path::new(path);
+    let mut file = File::open(path).unwrap();
+    let mut data = String::new();
+
+    file.read_to_string(&mut data).unwrap();
+
+    data
+}
+
+#[test_resources("src/derivation/tests/derivation_tests/*.drv")]
+fn check_serizaliation(path_to_drv_file: &str) {
+    let data = read_file(&format!("{}.json", path_to_drv_file));
+    let derivation: Derivation = serde_json::from_str(&data).expect("JSON was not well-formatted");
+
+    let mut serialized_derivation = String::new();
+    derivation.serialize(&mut serialized_derivation).unwrap();
+
+    let expected = read_file(path_to_drv_file);
+
+    assert_eq!(expected, serialized_derivation);
+}
+
+#[test_resources("src/derivation/tests/derivation_tests/*.drv")]
+fn validate(path_to_drv_file: &str) {
+    let data = read_file(&format!("{}.json", path_to_drv_file));
+    let derivation: Derivation = serde_json::from_str(&data).expect("JSON was not well-formatted");
+
+    derivation
+        .validate(true)
+        .expect("derivation failed to validate")
+}
+
+#[test_resources("src/derivation/tests/derivation_tests/*.drv")]
+fn check_to_aterm_string(path_to_drv_file: &str) {
+    let data = read_file(&format!("{}.json", path_to_drv_file));
+    let derivation: Derivation = serde_json::from_str(&data).expect("JSON was not well-formatted");
+
+    let expected = read_file(path_to_drv_file);
+
+    assert_eq!(expected, derivation.to_aterm_string());
+}
+
+#[test_case("bar","0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv"; "fixed_sha256")]
+#[test_case("foo", "4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv"; "simple-sha256")]
+#[test_case("bar", "ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv"; "fixed-sha1")]
+#[test_case("foo", "ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv"; "simple-sha1")]
+#[test_case("has-multi-out", "h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv"; "multiple-outputs")]
+#[test_case("structured-attrs", "9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv"; "structured-attrs")]
+#[test_case("unicode", "52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv"; "unicode")]
+fn derivation_path(name: &str, expected_path: &str) {
+    let data = read_file(&format!("{}/{}.json", RESOURCES_PATHS, expected_path));
+    let derivation: Derivation = serde_json::from_str(&data).expect("JSON was not well-formatted");
+
+    assert_eq!(
+        derivation.calculate_derivation_path(name).unwrap(),
+        StorePath::from_string(expected_path).unwrap()
+    );
+}
+
+/// This trims all output paths from a Derivation struct,
+/// by setting outputs[$outputName].path and environment[$outputName] to the empty string.
+fn derivation_with_trimmed_output_paths(derivation: &Derivation) -> Derivation {
+    let mut trimmed_env = derivation.environment.clone();
+    let mut trimmed_outputs = derivation.outputs.clone();
+
+    for (output_name, output) in &derivation.outputs {
+        trimmed_env.insert(output_name.clone(), "".to_string());
+        assert!(trimmed_outputs.contains_key(output_name));
+        trimmed_outputs.insert(
+            output_name.to_string(),
+            Output {
+                path: "".to_string(),
+                ..output.clone()
+            },
+        );
+    }
+
+    // replace environment and outputs with the trimmed variants
+    Derivation {
+        environment: trimmed_env,
+        outputs: trimmed_outputs,
+        ..derivation.clone()
+    }
+}
+
+#[test_case("0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv", "sha256:724f3e3634fce4cbbbd3483287b8798588e80280660b9a63fd13a1bc90485b33"; "fixed_sha256")]
+#[test_case("ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv", "sha256:c79aebd0ce3269393d4a1fde2cbd1d975d879b40f0bf40a48f550edc107fd5df";"fixed-sha1")]
+fn derivation_or_fod_hash(drv_path: &str, expected_nix_hash_string: &str) {
+    // read in the fixture
+    let data = read_file(&format!("{}/{}.json", RESOURCES_PATHS, drv_path));
+    let drv: Derivation = serde_json::from_str(&data).expect("must deserialize");
+
+    let actual = drv.derivation_or_fod_hash(|_| panic!("must not be called"));
+
+    assert_eq!(expected_nix_hash_string, actual.to_nix_hash_string());
+}
+
+#[test_case("bar","0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv"; "fixed_sha256")]
+#[test_case("foo", "4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv"; "simple-sha256")]
+#[test_case("bar", "ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv"; "fixed-sha1")]
+#[test_case("foo", "ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv"; "simple-sha1")]
+#[test_case("has-multi-out", "h32dahq0bx5rp1krcdx3a53asj21jvhk-has-multi-out.drv"; "multiple-outputs")]
+#[test_case("structured-attrs", "9lj1lkjm2ag622mh4h9rpy6j607an8g2-structured-attrs.drv"; "structured-attrs")]
+#[test_case("unicode", "52a9id8hx688hvlnz4d1n25ml1jdykz0-unicode.drv"; "unicode")]
+fn output_paths(name: &str, drv_path: &str) {
+    // read in the fixture
+    let data = read_file(&format!("{}/{}.json", RESOURCES_PATHS, drv_path));
+    let expected_derivation: Derivation = serde_json::from_str(&data).expect("must deserialize");
+
+    let mut derivation = derivation_with_trimmed_output_paths(&expected_derivation);
+
+    // calculate the derivation_or_fod_hash of derivation
+    // We don't expect the lookup function to be called for most derivations.
+    let calculated_derivation_or_fod_hash = derivation.derivation_or_fod_hash(|parent_drv_path| {
+        // 4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv may lookup /nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv
+        // ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv may lookup /nix/store/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv
+        if name == "foo"
+            && ((drv_path == "4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv"
+                && parent_drv_path == "/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv")
+                || (drv_path == "ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv"
+                    && parent_drv_path == "/nix/store/ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv"))
+        {
+            // do the lookup, by reading in the fixture of the requested
+            // drv_name, and calculating its drv replacement (on the non-stripped version)
+            // In a real-world scenario you would have already done this during construction.
+
+            let data = read_file(&format!(
+                "{}/{}.json",
+                RESOURCES_PATHS,
+                Path::new(parent_drv_path)
+                    .file_name()
+                    .unwrap()
+                    .to_string_lossy()
+            ));
+
+            let drv: Derivation = serde_json::from_str(&data).expect("must deserialize");
+
+            // calculate derivation_or_fod_hash for each parent.
+            // This may not trigger subsequent requests, as both parents are FOD.
+            drv.derivation_or_fod_hash(|_| panic!("must not lookup"))
+        } else {
+            // we only expect this to be called in the "foo" testcase, for the "bar derivations"
+            panic!("may only be called for foo testcase on bar derivations");
+        }
+    });
+
+    derivation
+        .calculate_output_paths(name, &calculated_derivation_or_fod_hash)
+        .unwrap();
+
+    // The derivation should now look like it was before
+    assert_eq!(expected_derivation, derivation);
+}
+
+/// Exercises the output path calculation functions like a constructing client
+/// (an implementation of builtins.derivation) would do:
+///
+/// ```nix
+/// rec {
+///   bar = builtins.derivation {
+///     name = "bar";
+///     builder = ":";
+///     system = ":";
+///     outputHash = "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba";
+///     outputHashAlgo = "sha256";
+///     outputHashMode = "recursive";
+///   };
+///
+///   foo = builtins.derivation {
+///     name = "foo";
+///     builder = ":";
+///     system = ":";
+///     inherit bar;
+///   };
+/// }
+/// ```
+/// It first assembles the bar derivation, does the output path calculation on
+/// it, then continues with the foo derivation.
+///
+/// The code ensures the resulting Derivations match our fixtures.
+#[test]
+fn output_path_construction() {
+    // create the bar derivation
+    let mut bar_drv = Derivation {
+        builder: ":".to_string(),
+        system: ":".to_string(),
+        ..Default::default()
+    };
+
+    // assemble bar env
+    let bar_env = &mut bar_drv.environment;
+    bar_env.insert("builder".to_string(), ":".to_string());
+    bar_env.insert("name".to_string(), "bar".to_string());
+    bar_env.insert("out".to_string(), "".to_string()); // will be calculated
+    bar_env.insert(
+        "outputHash".to_string(),
+        "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba".to_string(),
+    );
+    bar_env.insert("outputHashAlgo".to_string(), "sha256".to_string());
+    bar_env.insert("outputHashMode".to_string(), "recursive".to_string());
+    bar_env.insert("system".to_string(), ":".to_string());
+
+    // assemble bar outputs
+    bar_drv.outputs.insert(
+        "out".to_string(),
+        Output {
+            path: "".to_string(), // will be calculated
+            hash_with_mode: Some(crate::nixhash::NixHashWithMode::Recursive(NixHash {
+                digest: data_encoding::HEXLOWER
+                    .decode(
+                        "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba"
+                            .as_bytes(),
+                    )
+                    .unwrap(),
+                algo: crate::nixhash::HashAlgo::Sha256,
+            })),
+        },
+    );
+
+    // calculate bar output paths
+    let bar_calc_result = bar_drv.calculate_output_paths(
+        "bar",
+        &bar_drv.derivation_or_fod_hash(|_| panic!("is FOD, should not lookup")),
+    );
+    assert!(bar_calc_result.is_ok());
+
+    // ensure it matches our bar fixture
+    let bar_data = read_file(&format!(
+        "{}/{}.json",
+        RESOURCES_PATHS, "0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv"
+    ));
+    let bar_drv_expected: Derivation = serde_json::from_str(&bar_data).expect("must deserialize");
+    assert_eq!(bar_drv_expected, bar_drv);
+
+    // now construct foo, which requires bar_drv
+    // Note how we refer to the output path, drv name and replacement_str (with calculated output paths) of bar.
+    let bar_output_path = &bar_drv.outputs.get("out").expect("must exist").path;
+    let bar_drv_derivation_or_fod_hash =
+        bar_drv.derivation_or_fod_hash(|_| panic!("is FOD, should not lookup"));
+
+    let bar_drv_path = bar_drv
+        .calculate_derivation_path("bar")
+        .expect("must succeed");
+
+    // create foo derivation
+    let mut foo_drv = Derivation {
+        builder: ":".to_string(),
+        system: ":".to_string(),
+        ..Default::default()
+    };
+
+    // assemble foo env
+    let foo_env = &mut foo_drv.environment;
+    foo_env.insert("bar".to_string(), bar_output_path.to_string());
+    foo_env.insert("builder".to_string(), ":".to_string());
+    foo_env.insert("name".to_string(), "foo".to_string());
+    foo_env.insert("out".to_string(), "".to_string()); // will be calculated
+    foo_env.insert("system".to_string(), ":".to_string());
+
+    // asssemble foo outputs
+    foo_drv.outputs.insert(
+        "out".to_string(),
+        Output {
+            path: "".to_string(), // will be calculated
+            hash_with_mode: None,
+        },
+    );
+
+    // assemble foo input_derivations
+    foo_drv.input_derivations.insert(
+        bar_drv_path.to_absolute_path(),
+        BTreeSet::from(["out".to_string()]),
+    );
+
+    // calculate foo output paths
+    let foo_calc_result = foo_drv.calculate_output_paths(
+        "foo",
+        &foo_drv.derivation_or_fod_hash(|drv_path| {
+            if drv_path != "/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv" {
+                panic!("lookup called with unexpected drv_path: {}", drv_path);
+            }
+            bar_drv_derivation_or_fod_hash.clone()
+        }),
+    );
+    assert!(foo_calc_result.is_ok());
+
+    // ensure it matches our foo fixture
+    let foo_data = read_file(&format!(
+        "{}/{}.json",
+        RESOURCES_PATHS, "4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv",
+    ));
+    let foo_drv_expected: Derivation = serde_json::from_str(&foo_data).expect("must deserialize");
+    assert_eq!(foo_drv_expected, foo_drv);
+
+    assert_eq!(
+        StorePath::from_string("4wvvbi4jwn0prsdxb7vs673qa5h9gr7x-foo.drv").expect("must succeed"),
+        foo_drv
+            .calculate_derivation_path("foo")
+            .expect("must succeed")
+    );
+}
diff --git a/tvix/nix-compat/src/derivation/validate.rs b/tvix/nix-compat/src/derivation/validate.rs
new file mode 100644
index 000000000000..d8dc24a92ae1
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/validate.rs
@@ -0,0 +1,129 @@
+use crate::derivation::{Derivation, DerivationError};
+use crate::store_path::StorePath;
+
+impl Derivation {
+    /// validate ensures a Derivation struct is properly populated,
+    /// and returns a [DerivationError] if not.
+    ///
+    /// if `validate_output_paths` is set to false, the output paths are
+    /// excluded from validation.
+    ///
+    /// This is helpful to validate struct population before invoking
+    /// [Derivation::calculate_output_paths].
+    pub fn validate(&self, validate_output_paths: bool) -> Result<(), DerivationError> {
+        // Ensure the number of outputs is > 1
+        if self.outputs.is_empty() {
+            return Err(DerivationError::NoOutputs());
+        }
+
+        // Validate all outputs
+        for (output_name, output) in &self.outputs {
+            // empty output names are invalid.
+            //
+            // `drv` is an invalid output name too, as this would cause
+            // a `builtins.derivation` call to return an attrset with a
+            // `drvPath` key (which already exists) and has a different
+            // meaning.
+            //
+            // Other output names that don't match the name restrictions from
+            // [StorePath] will fail the [StorePath::validate_name] check.
+            if output_name.is_empty()
+                || output_name == "drv"
+                || StorePath::validate_name(output_name).is_err()
+            {
+                return Err(DerivationError::InvalidOutputName(output_name.to_string()));
+            }
+
+            if output.is_fixed() {
+                if self.outputs.len() != 1 {
+                    return Err(DerivationError::MoreThanOneOutputButFixed());
+                }
+                if output_name != "out" {
+                    return Err(DerivationError::InvalidOutputNameForFixed(
+                        output_name.to_string(),
+                    ));
+                }
+
+                break;
+            }
+
+            if let Err(e) = output.validate(validate_output_paths) {
+                return Err(DerivationError::InvalidOutput(output_name.to_string(), e));
+            }
+        }
+
+        // Validate all input_derivations
+        for (input_derivation_path, output_names) in &self.input_derivations {
+            // Validate input_derivation_path
+            if let Err(e) = StorePath::from_absolute_path(input_derivation_path) {
+                return Err(DerivationError::InvalidInputDerivationPath(
+                    input_derivation_path.to_string(),
+                    e,
+                ));
+            }
+
+            if !input_derivation_path.ends_with(".drv") {
+                return Err(DerivationError::InvalidInputDerivationPrefix(
+                    input_derivation_path.to_string(),
+                ));
+            }
+
+            if output_names.is_empty() {
+                return Err(DerivationError::EmptyInputDerivationOutputNames(
+                    input_derivation_path.to_string(),
+                ));
+            }
+
+            for output_name in output_names.iter() {
+                // empty output names are invalid.
+                //
+                // `drv` is an invalid output name too, as this would cause
+                // a `builtins.derivation` call to return an attrset with a
+                // `drvPath` key (which already exists) and has a different
+                // meaning.
+                //
+                // Other output names that don't match the name restrictions from
+                // [StorePath] will fail the [StorePath::validate_name] check.
+                if output_name.is_empty()
+                    || output_name == "drv"
+                    || StorePath::validate_name(output_name).is_err()
+                {
+                    return Err(DerivationError::InvalidInputDerivationOutputName(
+                        input_derivation_path.to_string(),
+                        output_name.to_string(),
+                    ));
+                }
+            }
+        }
+
+        // Validate all input_sources
+        for input_source in self.input_sources.iter() {
+            if let Err(e) = StorePath::from_absolute_path(input_source) {
+                return Err(DerivationError::InvalidInputSourcesPath(
+                    input_source.to_string(),
+                    e,
+                ));
+            }
+        }
+
+        // validate platform
+        if self.system.is_empty() {
+            return Err(DerivationError::InvalidPlatform(self.system.to_string()));
+        }
+
+        // validate builder
+        if self.builder.is_empty() {
+            return Err(DerivationError::InvalidBuilder(self.builder.to_string()));
+        }
+
+        // validate env, none of the keys may be empty.
+        // We skip the `name` validation seen in go-nix.
+        for k in self.environment.keys() {
+            if k.is_empty() {
+                return Err(DerivationError::InvalidEnvironmentKey(k.to_string()));
+            }
+        }
+
+        Ok(())
+    }
+}
diff --git a/tvix/nix-compat/src/derivation/write.rs b/tvix/nix-compat/src/derivation/write.rs
new file mode 100644
index 000000000000..52166294e078
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/write.rs
@@ -0,0 +1,190 @@
+//! This module implements the serialisation of derivations into the
+//! [ATerm][] format used by C++ Nix.
+//!
+//! [ATerm]: http://program-transformation.org/Tools/ATermFormat.html
+
+use crate::derivation::output::Output;
+use crate::derivation::string_escape::escape_string;
+use std::collections::BTreeSet;
+use std::{collections::BTreeMap, fmt, fmt::Write};
+
+pub const DERIVATION_PREFIX: &str = "Derive";
+pub const PAREN_OPEN: char = '(';
+pub const PAREN_CLOSE: char = ')';
+pub const BRACKET_OPEN: char = '[';
+pub const BRACKET_CLOSE: char = ']';
+pub const COMMA: char = ',';
+pub const QUOTE: char = '"';
+
+fn write_array_elements(
+    writer: &mut impl Write,
+    quote: bool,
+    open: &str,
+    closing: &str,
+    elements: Vec<&str>,
+) -> Result<(), fmt::Error> {
+    writer.write_str(open)?;
+
+    for (index, element) in elements.iter().enumerate() {
+        if index > 0 {
+            writer.write_char(COMMA)?;
+        }
+
+        if quote {
+            writer.write_char(QUOTE)?;
+        }
+
+        writer.write_str(element)?;
+
+        if quote {
+            writer.write_char(QUOTE)?;
+        }
+    }
+
+    writer.write_str(closing)?;
+
+    Ok(())
+}
+
+pub fn write_outputs(
+    writer: &mut impl Write,
+    outputs: &BTreeMap<String, Output>,
+) -> Result<(), fmt::Error> {
+    writer.write_char(BRACKET_OPEN)?;
+    for (ii, (output_name, output)) in outputs.iter().enumerate() {
+        if ii > 0 {
+            writer.write_char(COMMA)?;
+        }
+
+        let mut elements: Vec<&str> = vec![output_name, &output.path];
+
+        let (e2, e3) = match &output.hash_with_mode {
+            Some(hash) => match hash {
+                crate::nixhash::NixHashWithMode::Flat(h) => (
+                    h.algo.to_string(),
+                    data_encoding::HEXLOWER.encode(&h.digest),
+                ),
+                crate::nixhash::NixHashWithMode::Recursive(h) => (
+                    format!("r:{}", h.algo),
+                    data_encoding::HEXLOWER.encode(&h.digest),
+                ),
+            },
+            None => ("".to_string(), "".to_string()),
+        };
+
+        elements.push(&e2);
+        elements.push(&e3);
+
+        write_array_elements(
+            writer,
+            true,
+            &PAREN_OPEN.to_string(),
+            &PAREN_CLOSE.to_string(),
+            elements,
+        )?
+    }
+    writer.write_char(BRACKET_CLOSE)?;
+
+    Ok(())
+}
+
+pub fn write_input_derivations(
+    writer: &mut impl Write,
+    input_derivations: &BTreeMap<String, BTreeSet<String>>,
+) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+    writer.write_char(BRACKET_OPEN)?;
+
+    for (ii, (input_derivation_path, input_derivation)) in input_derivations.iter().enumerate() {
+        if ii > 0 {
+            writer.write_char(COMMA)?;
+        }
+
+        writer.write_char(PAREN_OPEN)?;
+        writer.write_char(QUOTE)?;
+        writer.write_str(input_derivation_path.as_str())?;
+        writer.write_char(QUOTE)?;
+        writer.write_char(COMMA)?;
+
+        write_array_elements(
+            writer,
+            true,
+            &BRACKET_OPEN.to_string(),
+            &BRACKET_CLOSE.to_string(),
+            input_derivation.iter().map(|s| &**s).collect(),
+        )?;
+
+        writer.write_char(PAREN_CLOSE)?;
+    }
+
+    writer.write_char(BRACKET_CLOSE)?;
+
+    Ok(())
+}
+
+pub fn write_input_sources(
+    writer: &mut impl Write,
+    input_sources: &BTreeSet<String>,
+) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+
+    write_array_elements(
+        writer,
+        true,
+        &BRACKET_OPEN.to_string(),
+        &BRACKET_CLOSE.to_string(),
+        input_sources.iter().map(|s| &**s).collect(),
+    )?;
+
+    Ok(())
+}
+
+pub fn write_system(writer: &mut impl Write, platform: &str) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+    writer.write_str(escape_string(platform).as_str())?;
+    Ok(())
+}
+
+pub fn write_builder(writer: &mut impl Write, builder: &str) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+    writer.write_str(escape_string(builder).as_str())?;
+    Ok(())
+}
+pub fn write_arguments(writer: &mut impl Write, arguments: &[String]) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+    write_array_elements(
+        writer,
+        true,
+        &BRACKET_OPEN.to_string(),
+        &BRACKET_CLOSE.to_string(),
+        arguments.iter().map(|s| &**s).collect(),
+    )?;
+
+    Ok(())
+}
+
+pub fn write_enviroment(
+    writer: &mut impl Write,
+    environment: &BTreeMap<String, String>,
+) -> Result<(), fmt::Error> {
+    writer.write_char(COMMA)?;
+    writer.write_char(BRACKET_OPEN)?;
+
+    for (ii, (key, environment)) in environment.iter().enumerate() {
+        if ii > 0 {
+            writer.write_char(COMMA)?;
+        }
+
+        write_array_elements(
+            writer,
+            false,
+            &PAREN_OPEN.to_string(),
+            &PAREN_CLOSE.to_string(),
+            vec![&escape_string(key), &escape_string(environment)],
+        )?;
+    }
+
+    writer.write_char(BRACKET_CLOSE)?;
+
+    Ok(())
+}
diff --git a/tvix/nix-compat/src/lib.rs b/tvix/nix-compat/src/lib.rs
new file mode 100644
index 000000000000..37d79f38fb37
--- /dev/null
+++ b/tvix/nix-compat/src/lib.rs
@@ -0,0 +1,5 @@
+pub mod derivation;
+pub mod nar;
+pub mod nixbase32;
+pub mod nixhash;
+pub mod store_path;
diff --git a/tvix/nix-compat/src/nar/mod.rs b/tvix/nix-compat/src/nar/mod.rs
new file mode 100644
index 000000000000..d3baa817825a
--- /dev/null
+++ b/tvix/nix-compat/src/nar/mod.rs
@@ -0,0 +1 @@
+pub mod writer;
diff --git a/tvix/nix-compat/src/nar/writer/mod.rs b/tvix/nix-compat/src/nar/writer/mod.rs
new file mode 100644
index 000000000000..f24b69883876
--- /dev/null
+++ b/tvix/nix-compat/src/nar/writer/mod.rs
@@ -0,0 +1,219 @@
+//! Implements an interface for writing the Nix archive format (NAR).
+//!
+//! NAR files (and their hashed representations) are used in C++ Nix for
+//! addressing fixed-output derivations and a variety of other things.
+//!
+//! NAR files can be output to any type that implements [`Write`], and content
+//! can be read from any type that implementes [`BufRead`].
+//!
+//! Writing a single file might look like this:
+//!
+//! ```rust
+//! # use std::io::BufReader;
+//! # let some_file: Vec<u8> = vec![0, 1, 2, 3, 4];
+//!
+//! // Output location to write the NAR to.
+//! let mut sink: Vec<u8> = Vec::new();
+//!
+//! // Instantiate writer for this output location.
+//! let mut nar = nix_compat::nar::writer::open(&mut sink)?;
+//!
+//! // Acquire metadata for the single file to output, and pass it in a
+//! // `BufRead`-implementing type.
+//!
+//! let executable = false;
+//! let size = some_file.len() as u64;
+//! let mut reader = BufReader::new(some_file.as_slice());
+//! nar.file(executable, size, &mut reader)?;
+//! # Ok::<(), std::io::Error>(())
+//! ```
+
+use std::io::{
+    self, BufRead,
+    ErrorKind::{InvalidInput, UnexpectedEof},
+    Write,
+};
+
+mod wire;
+
+/// Convenience type alias for types implementing [`Write`].
+pub type Writer<'a> = dyn Write + 'a;
+
+/// Create a new NAR, writing the output to the specified writer.
+pub fn open<'a, 'w: 'a>(writer: &'a mut Writer<'w>) -> io::Result<Node<'a, 'w>> {
+    let mut node = Node { writer };
+    node.write(&wire::TOK_NAR)?;
+    Ok(node)
+}
+
+/// Single node in a NAR file.
+///
+/// A NAR can be thought of as a tree of nodes represented by this type. Each
+/// node can be a file, a symlink or a directory containing other nodes.
+pub struct Node<'a, 'w: 'a> {
+    writer: &'a mut Writer<'w>,
+}
+
+impl<'a, 'w> Node<'a, 'w> {
+    fn write(&mut self, data: &[u8]) -> io::Result<()> {
+        self.writer.write_all(data)
+    }
+
+    fn pad(&mut self, n: u64) -> io::Result<()> {
+        match (n & 7) as usize {
+            0 => Ok(()),
+            n => self.write(&[0; 8][n..]),
+        }
+    }
+
+    /// Make this node a symlink.
+    pub fn symlink(mut self, target: &str) -> io::Result<()> {
+        debug_assert!(
+            target.len() <= wire::MAX_TARGET_LEN,
+            "target.len() > {}",
+            wire::MAX_TARGET_LEN
+        );
+        debug_assert!(
+            !target.contains('\0'),
+            "invalid target characters: {target:?}"
+        );
+        debug_assert!(!target.is_empty(), "empty target");
+
+        self.write(&wire::TOK_SYM)?;
+        self.write(&target.len().to_le_bytes())?;
+        self.write(target.as_bytes())?;
+        self.pad(target.len() as u64)?;
+        self.write(&wire::TOK_PAR)?;
+        Ok(())
+    }
+
+    /// Make this node a single file.
+    pub fn file(mut self, executable: bool, size: u64, reader: &mut dyn BufRead) -> io::Result<()> {
+        self.write(if executable {
+            &wire::TOK_EXE
+        } else {
+            &wire::TOK_REG
+        })?;
+
+        self.write(&size.to_le_bytes())?;
+
+        let mut need = size;
+        while need != 0 {
+            let data = reader.fill_buf()?;
+
+            if data.is_empty() {
+                return Err(UnexpectedEof.into());
+            }
+
+            let n = need.min(data.len() as u64) as usize;
+            self.write(&data[..n])?;
+
+            need -= n as u64;
+            reader.consume(n);
+        }
+
+        // bail if there's still data left in the passed reader.
+        // This uses the same code as [BufRead::has_data_left] (unstable).
+        if reader.fill_buf().map(|b| !b.is_empty())? {
+            return Err(io::Error::new(
+                InvalidInput,
+                "reader contained more data than specified size",
+            ));
+        }
+
+        self.pad(size)?;
+        self.write(&wire::TOK_PAR)?;
+
+        Ok(())
+    }
+
+    /// Make this node a directory, the content of which is set using the
+    /// resulting [`Directory`] value.
+    pub fn directory(mut self) -> io::Result<Directory<'a, 'w>> {
+        self.write(&wire::TOK_DIR)?;
+        Ok(Directory::new(self))
+    }
+}
+
+#[cfg(debug_assertions)]
+type Name = String;
+#[cfg(not(debug_assertions))]
+type Name = ();
+
+fn into_name(_name: &str) -> Name {
+    #[cfg(debug_assertions)]
+    _name.to_owned()
+}
+
+/// Content of a NAR node that represents a directory.
+pub struct Directory<'a, 'w> {
+    node: Node<'a, 'w>,
+    prev_name: Option<Name>,
+}
+
+impl<'a, 'w> Directory<'a, 'w> {
+    fn new(node: Node<'a, 'w>) -> Self {
+        Self {
+            node,
+            prev_name: None,
+        }
+    }
+
+    /// Add an entry to the directory.
+    ///
+    /// The entry is simply another [`Node`], which can then be filled like the
+    /// root of a NAR (including, of course, by nesting directories).
+    pub fn entry(&mut self, name: &str) -> io::Result<Node<'_, 'w>> {
+        debug_assert!(
+            name.len() <= wire::MAX_NAME_LEN,
+            "name.len() > {}",
+            wire::MAX_NAME_LEN
+        );
+        debug_assert!(!["", ".", ".."].contains(&name), "invalid name: {name:?}");
+        debug_assert!(
+            !name.contains(['/', '\0']),
+            "invalid name characters: {name:?}"
+        );
+
+        match self.prev_name {
+            None => {
+                self.prev_name = Some(into_name(name));
+            }
+            Some(ref mut _prev_name) => {
+                #[cfg(debug_assertions)]
+                {
+                    assert!(
+                        &**_prev_name < name,
+                        "misordered names: {_prev_name:?} >= {name:?}"
+                    );
+                    _prev_name.clear();
+                    _prev_name.push_str(name);
+                }
+                self.node.write(&wire::TOK_PAR)?;
+            }
+        }
+
+        self.node.write(&wire::TOK_ENT)?;
+        self.node.write(&name.len().to_le_bytes())?;
+        self.node.write(name.as_bytes())?;
+        self.node.pad(name.len() as u64)?;
+        self.node.write(&wire::TOK_NOD)?;
+
+        Ok(Node {
+            writer: &mut *self.node.writer,
+        })
+    }
+
+    /// Close a directory and write terminators for the directory to the NAR.
+    ///
+    /// **Important:** This *must* be called when all entries have been written
+    /// in a directory, otherwise the resulting NAR file will be invalid.
+    pub fn close(mut self) -> io::Result<()> {
+        if self.prev_name.is_some() {
+            self.node.write(&wire::TOK_PAR)?;
+        }
+
+        self.node.write(&wire::TOK_PAR)?;
+        Ok(())
+    }
+}
diff --git a/tvix/nix-compat/src/nar/writer/wire.rs b/tvix/nix-compat/src/nar/writer/wire.rs
new file mode 100644
index 000000000000..98581ae3aa7c
--- /dev/null
+++ b/tvix/nix-compat/src/nar/writer/wire.rs
@@ -0,0 +1,46 @@
+pub const MAX_NAME_LEN: usize = 255;
+pub const MAX_TARGET_LEN: usize = 4095;
+
+#[cfg(test)]
+fn token(xs: &[&str]) -> Vec<u8> {
+    let mut out = vec![];
+    for x in xs {
+        let len = x.len() as u64;
+        out.extend_from_slice(&len.to_le_bytes());
+        out.extend_from_slice(x.as_bytes());
+
+        let n = x.len() & 7;
+        if n != 0 {
+            const ZERO: [u8; 8] = [0; 8];
+            out.extend_from_slice(&ZERO[n..]);
+        }
+    }
+    out
+}
+
+pub const TOK_NAR: [u8; 56] = *b"\x0d\0\0\0\0\0\0\0nix-archive-1\0\0\0\x01\0\0\0\0\0\0\0(\0\0\0\0\0\0\0\x04\0\0\0\0\0\0\0type\0\0\0\0";
+pub const TOK_REG: [u8; 32] = *b"\x07\0\0\0\0\0\0\0regular\0\x08\0\0\0\0\0\0\0contents";
+pub const TOK_EXE: [u8; 64] = *b"\x07\0\0\0\0\0\0\0regular\0\x0a\0\0\0\0\0\0\0executable\0\0\0\0\0\0\0\0\0\0\0\0\0\0\x08\0\0\0\0\0\0\0contents";
+pub const TOK_SYM: [u8; 32] = *b"\x07\0\0\0\0\0\0\0symlink\0\x06\0\0\0\0\0\0\0target\0\0";
+pub const TOK_DIR: [u8; 24] = *b"\x09\0\0\0\0\0\0\0directory\0\0\0\0\0\0\0";
+pub const TOK_ENT: [u8; 48] = *b"\x05\0\0\0\0\0\0\0entry\0\0\0\x01\0\0\0\0\0\0\0(\0\0\0\0\0\0\0\x04\0\0\0\0\0\0\0name\0\0\0\0";
+pub const TOK_NOD: [u8; 48] = *b"\x04\0\0\0\0\0\0\0node\0\0\0\0\x01\0\0\0\0\0\0\0(\0\0\0\0\0\0\0\x04\0\0\0\0\0\0\0type\0\0\0\0";
+pub const TOK_PAR: [u8; 16] = *b"\x01\0\0\0\0\0\0\0)\0\0\0\0\0\0\0";
+
+#[test]
+fn tokens() {
+    let cases: &[(&[u8], &[&str])] = &[
+        (&TOK_NAR, &["nix-archive-1", "(", "type"]),
+        (&TOK_REG, &["regular", "contents"]),
+        (&TOK_EXE, &["regular", "executable", "", "contents"]),
+        (&TOK_SYM, &["symlink", "target"]),
+        (&TOK_DIR, &["directory"]),
+        (&TOK_ENT, &["entry", "(", "name"]),
+        (&TOK_NOD, &["node", "(", "type"]),
+        (&TOK_PAR, &[")"]),
+    ];
+
+    for &(tok, xs) in cases {
+        assert_eq!(tok, token(xs));
+    }
+}
diff --git a/tvix/nix-compat/src/nixbase32.rs b/tvix/nix-compat/src/nixbase32.rs
new file mode 100644
index 000000000000..3d1c276c63bb
--- /dev/null
+++ b/tvix/nix-compat/src/nixbase32.rs
@@ -0,0 +1,167 @@
+//! Implements the slightly odd "base32" encoding that's used in Nix.
+//!
+//! Nix uses a custom alphabet. Contrary to other implementations (RFC4648),
+//! encoding to "nix base32" doesn't use any padding, and reads in characters
+//! in reverse order.
+//!
+//! This is also the main reason why we can't use `data_encoding::Encoding` -
+//! it gets things wrong if there normally would be a need for padding.
+
+use std::fmt::Write;
+
+use thiserror::Error;
+
+const ALPHABET: &[u8; 32] = b"0123456789abcdfghijklmnpqrsvwxyz";
+
+/// Errors that can occur while decoding nixbase32-encoded data.
+#[derive(Debug, Eq, PartialEq, Error)]
+pub enum Nixbase32DecodeError {
+    #[error("character {0:x} not in alphabet")]
+    CharacterNotInAlphabet(u8),
+    #[error("nonzero carry")]
+    NonzeroCarry(),
+}
+
+/// Returns encoded input
+pub fn encode(input: &[u8]) -> String {
+    let output_len = encode_len(input.len());
+    let mut output = String::with_capacity(output_len);
+
+    if output_len > 0 {
+        for n in (0..=output_len - 1).rev() {
+            let b = n * 5; // bit offset within the entire input
+            let i = b / 8; // input byte index
+            let j = b % 8; // bit offset within that input byte
+
+            let mut c = input[i] >> j;
+            if i + 1 < input.len() {
+                // we want to right shift, and discard shifted out bits (unchecked)
+                // To do this without panicing, we need to do the shifting in u16
+                // and convert back to u8 afterwards.
+                c |= ((input[i + 1] as u16) << (8 - j as u16)) as u8
+            }
+
+            output
+                .write_char(ALPHABET[(c & 0x1f) as usize] as char)
+                .unwrap();
+        }
+    }
+
+    output
+}
+
+/// This maps a nixbase32-encoded character to its binary representation, which
+/// is also the index of the character in the alphabet.
+fn decode_char(encoded_char: &u8) -> Option<u8> {
+    Some(match encoded_char {
+        b'0'..=b'9' => encoded_char - b'0',
+        b'a'..=b'd' => encoded_char - b'a' + 10_u8,
+        b'f'..=b'n' => encoded_char - b'f' + 14_u8,
+        b'p'..=b's' => encoded_char - b'p' + 23_u8,
+        b'v'..=b'z' => encoded_char - b'v' + 27_u8,
+        _ => return None,
+    })
+}
+
+/// Returns decoded input
+pub fn decode(input: &[u8]) -> Result<Vec<u8>, Nixbase32DecodeError> {
+    let output_len = decode_len(input.len());
+    let mut output: Vec<u8> = vec![0x00; output_len];
+
+    // loop over all characters in reverse, and keep the iteration count in n.
+    for (n, c) in input.iter().rev().enumerate() {
+        match decode_char(c) {
+            None => return Err(Nixbase32DecodeError::CharacterNotInAlphabet(*c)),
+            Some(c_decoded) => {
+                let b = n * 5;
+                let i = b / 8;
+                let j = b % 8;
+
+                let val = (c_decoded as u16).rotate_left(j as u32);
+                output[i] |= (val & 0x00ff) as u8;
+                let carry = ((val & 0xff00) >> 8) as u8;
+
+                // if we're at the end of dst…
+                if i == output_len - 1 {
+                    // but have a nonzero carry, the encoding is invalid.
+                    if carry != 0 {
+                        return Err(Nixbase32DecodeError::NonzeroCarry());
+                    }
+                } else {
+                    output[i + 1] |= carry;
+                }
+            }
+        }
+    }
+
+    Ok(output)
+}
+
+/// Returns the decoded length of an input of length len.
+pub fn decode_len(len: usize) -> usize {
+    (len * 5) / 8
+}
+
+/// Returns the encoded length of an input of length len
+pub fn encode_len(len: usize) -> usize {
+    if len == 0 {
+        return 0;
+    }
+    (len * 8 - 1) / 5 + 1
+}
+
+#[cfg(test)]
+mod tests {
+    use test_case::test_case;
+
+    #[test_case("", vec![] ; "empty bytes")]
+    #[test_case("0z", vec![0x1f]; "one byte")]
+    #[test_case("00bgd045z0d4icpbc2yyz4gx48ak44la", vec![
+                 0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a,
+                 0xf8, 0x85, 0x80, 0xf6, 0x16, 0x00]; "store path")]
+    #[test_case("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", vec![
+        0xb3, 0xa2, 0x4d, 0xe9, 0x7a, 0x8f, 0xdb, 0xc8, 0x35, 0xb9, 0x83, 0x31, 0x69, 0x50, 0x10, 0x30,
+        0xb8, 0x97, 0x70, 0x31, 0xbc, 0xb5, 0x4b, 0x3b, 0x3a, 0xc1, 0x37, 0x40, 0xf8, 0x46, 0xab, 0x30,
+    ]; "sha256")]
+    fn encode(enc: &str, dec: Vec<u8>) {
+        assert_eq!(enc, super::encode(&dec));
+    }
+
+    #[test_case("", Some(vec![]) ; "empty bytes")]
+    #[test_case("0z", Some(vec![0x1f]); "one byte")]
+    #[test_case("00bgd045z0d4icpbc2yyz4gx48ak44la", Some(vec![
+                 0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a,
+                 0xf8, 0x85, 0x80, 0xf6, 0x16, 0x00]); "store path")]
+    #[test_case("0c5b8vw40dy178xlpddw65q9gf1h2186jcc3p4swinwggbllv8mk", Some(vec![
+        0xb3, 0xa2, 0x4d, 0xe9, 0x7a, 0x8f, 0xdb, 0xc8, 0x35, 0xb9, 0x83, 0x31, 0x69, 0x50, 0x10, 0x30,
+        0xb8, 0x97, 0x70, 0x31, 0xbc, 0xb5, 0x4b, 0x3b, 0x3a, 0xc1, 0x37, 0x40, 0xf8, 0x46, 0xab, 0x30,
+    ]); "sha256")]
+    // this is invalid encoding, because it encodes 10 1-bytes, so the carry
+    // would be 2 1-bytes
+    #[test_case("zz", None; "invalid encoding-1")]
+    // this is an even more specific example - it'd decode as 00000000 11
+    #[test_case("c0", None; "invalid encoding-2")]
+
+    fn decode(enc: &str, dec: Option<Vec<u8>>) {
+        match dec {
+            Some(dec) => {
+                // The decode needs to match what's passed in dec
+                assert_eq!(dec, super::decode(enc.as_bytes()).unwrap());
+            }
+            None => {
+                // the decode needs to be an error
+                assert!(super::decode(enc.as_bytes()).is_err());
+            }
+        }
+    }
+
+    #[test]
+    fn encode_len() {
+        assert_eq!(super::encode_len(20), 32)
+    }
+
+    #[test]
+    fn decode_len() {
+        assert_eq!(super::decode_len(32), 20)
+    }
+}
diff --git a/tvix/nix-compat/src/nixhash/algos.rs b/tvix/nix-compat/src/nixhash/algos.rs
new file mode 100644
index 000000000000..d6b0bf47bdb7
--- /dev/null
+++ b/tvix/nix-compat/src/nixhash/algos.rs
@@ -0,0 +1,39 @@
+use std::fmt::Display;
+
+use serde::{Deserialize, Serialize};
+
+use crate::nixhash::Error;
+
+/// This are the hash algorithms supported by cppnix.
+#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
+pub enum HashAlgo {
+    Md5,
+    Sha1,
+    Sha256,
+    Sha512,
+}
+
+impl Display for HashAlgo {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match &self {
+            HashAlgo::Md5 => write!(f, "md5"),
+            HashAlgo::Sha1 => write!(f, "sha1"),
+            HashAlgo::Sha256 => write!(f, "sha256"),
+            HashAlgo::Sha512 => write!(f, "sha512"),
+        }
+    }
+}
+
+impl TryFrom<&str> for HashAlgo {
+    type Error = Error;
+
+    fn try_from(algo_str: &str) -> Result<Self, Self::Error> {
+        match algo_str {
+            "md5" => Ok(Self::Md5),
+            "sha1" => Ok(Self::Sha1),
+            "sha256" => Ok(Self::Sha256),
+            "sha512" => Ok(Self::Sha512),
+            _ => Err(Error::InvalidAlgo(algo_str.to_string())),
+        }
+    }
+}
diff --git a/tvix/nix-compat/src/nixhash/mod.rs b/tvix/nix-compat/src/nixhash/mod.rs
new file mode 100644
index 000000000000..dccba7a5ba27
--- /dev/null
+++ b/tvix/nix-compat/src/nixhash/mod.rs
@@ -0,0 +1,454 @@
+use crate::nixbase32;
+use data_encoding::{BASE64, BASE64_NOPAD, HEXLOWER};
+use thiserror::Error;
+
+mod algos;
+mod with_mode;
+
+pub use algos::HashAlgo;
+pub use with_mode::NixHashWithMode;
+
+/// Nix allows specifying hashes in various encodings, and magically just
+/// derives the encoding.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct NixHash {
+    pub digest: Vec<u8>,
+
+    pub algo: HashAlgo,
+}
+
+impl NixHash {
+    /// Constructs a new [NixHash] by specifying [HashAlgo] and digest.
+    pub fn new(algo: HashAlgo, digest: Vec<u8>) -> Self {
+        Self { algo, digest }
+    }
+
+    /// Formats a [NixHash] in the Nix default hash format,
+    /// which is the algo, followed by a colon, then the lower hex encoded digest.
+    pub fn to_nix_hash_string(&self) -> String {
+        format!("{}:{}", self.algo, HEXLOWER.encode(&self.digest))
+    }
+}
+
+/// Errors related to NixHash construction.
+#[derive(Debug, Error)]
+pub enum Error {
+    #[error("invalid hash algo: {0}")]
+    InvalidAlgo(String),
+    #[error("invalid SRI string: {0}")]
+    InvalidSRI(String),
+    #[error("invalid encoded digest length '{0}' for algo {1}")]
+    InvalidEncodedDigestLength(usize, HashAlgo),
+    #[error("invalid base16 encoding: {0}")]
+    InvalidBase16Encoding(data_encoding::DecodeError),
+    #[error("invalid base32 encoding: {0}")]
+    InvalidBase32Encoding(nixbase32::Nixbase32DecodeError),
+    #[error("invalid base64 encoding: {0}")]
+    InvalidBase64Encoding(data_encoding::DecodeError),
+    #[error("conflicting hash algo: {0} (hash_algo) vs {1} (inline)")]
+    ConflictingHashAlgos(String, String),
+    #[error("missing inline hash algo, but no externally-specified algo: {0}")]
+    MissingInlineHashAlgo(String),
+}
+
+/// parses a string to a nix hash.
+///
+/// Hashes can be:
+/// - Nix hash strings
+/// - SRI hashes
+/// - bare digests
+///
+/// Encoding for Nix hash strings or bare digests can be:
+/// - base16 (lowerhex),
+/// - nixbase32,
+/// - base64 (StdEncoding)
+/// - sri string
+///
+/// The encoding is derived from the length of the string and the hash type.
+/// The hash is communicated out-of-band, but might also be in-band (in the
+/// case of a nix hash string or SRI), in which it needs to be consistent with the
+/// one communicated out-of-band.
+pub fn from_str(s: &str, algo_str: Option<&str>) -> Result<NixHash, Error> {
+    // validate algo_str, construct hash_algo
+    let algo: Option<HashAlgo> = match &algo_str {
+        Some("sha1") => Some(HashAlgo::Sha1),
+        Some("sha256") => Some(HashAlgo::Sha256),
+        Some("sha512") => Some(HashAlgo::Sha512),
+        Some("md5") => Some(HashAlgo::Md5),
+        Some(e) => return Err(Error::InvalidAlgo(e.to_string())),
+        None => None,
+    };
+
+    // peek at the beginning of the string. Let's detect the SRI path first.
+    if s.starts_with("sha1-")
+        || s.starts_with("sha256-")
+        || s.starts_with("sha512-")
+        || s.starts_with("md5-")
+    {
+        let parsed_nixhash = from_sri_str(s)?;
+        // ensure the algo matches with what has been passed externally, if so.
+        if let Some(algo) = algo {
+            if algo != parsed_nixhash.algo {
+                return Err(Error::ConflictingHashAlgos(
+                    algo.to_string(),
+                    parsed_nixhash.algo.to_string(),
+                ));
+            }
+        }
+        return Ok(parsed_nixhash);
+    }
+
+    // Now, peek at the beginning again to see if it's a Nix Hash
+    if s.starts_with("sha1:")
+        || s.starts_with("sha256:")
+        || s.starts_with("sha512:")
+        || s.starts_with("md5:")
+    {
+        let parsed_nixhash = from_nix_str(s)?;
+        // ensure the algo matches with what has been passed externally, if so.
+        if let Some(algo) = algo {
+            if algo != parsed_nixhash.algo {
+                return Err(Error::ConflictingHashAlgos(
+                    algo.to_string(),
+                    parsed_nixhash.algo.to_string(),
+                ));
+            }
+        }
+        return Ok(parsed_nixhash);
+    }
+
+    // In all other cases, we assume a bare digest, so there MUST be an externally-passed algo.
+    match algo {
+        // Fail if there isn't.
+        None => Err(Error::MissingInlineHashAlgo(s.to_string())),
+        Some(algo) => decode_digest(s, algo),
+    }
+}
+
+/// Parses a Nix hash string ($algo:$digest) to a NixHash.
+pub fn from_nix_str(s: &str) -> Result<NixHash, Error> {
+    if let Some(rest) = s.strip_prefix("sha1:") {
+        decode_digest(rest, HashAlgo::Sha1)
+    } else if let Some(rest) = s.strip_prefix("sha256:") {
+        decode_digest(rest, HashAlgo::Sha256)
+    } else if let Some(rest) = s.strip_prefix("sha512:") {
+        decode_digest(rest, HashAlgo::Sha512)
+    } else if let Some(rest) = s.strip_prefix("md5:") {
+        decode_digest(rest, HashAlgo::Md5)
+    } else {
+        Err(Error::InvalidAlgo(s.to_string()))
+    }
+}
+
+/// Parses a Nix SRI string to a NixHash.
+/// Contrary to the SRI spec, Nix doesn't support SRI strings with multiple hashes,
+/// only supports sha256 and sha512 from the spec, and supports sha1 and md5
+/// additionally.
+/// It also accepts SRI strings where the base64 has an with invalid padding.
+pub fn from_sri_str(s: &str) -> Result<NixHash, Error> {
+    // try to find the first occurence of "-"
+    let idx = s.as_bytes().iter().position(|&e| e == b'-');
+
+    if idx.is_none() {
+        return Err(Error::InvalidSRI(s.to_string()));
+    }
+
+    let idx = idx.unwrap();
+
+    // try to map the part before that `-` to a supported hash algo:
+    let algo: HashAlgo = s[..idx].try_into()?;
+
+    // the rest should be the digest (as Nix doesn't support more than one hash in an SRI string).
+    let encoded_digest = &s[idx + 1..];
+    let actual_len = encoded_digest.as_bytes().len();
+
+    // verify the digest length matches what we'd expect from the hash function,
+    // and then either try decoding as BASE64 or BASE64_NOPAD.
+    // This will also reject SRI strings with more than one hash, because the length won't match
+    if actual_len == BASE64.encode_len(hash_algo_length(&algo)) {
+        let digest: Vec<u8> = BASE64
+            .decode(encoded_digest.as_bytes())
+            .map_err(Error::InvalidBase64Encoding)?;
+        Ok(NixHash { digest, algo })
+    } else if actual_len == BASE64_NOPAD.encode_len(hash_algo_length(&algo)) {
+        let digest: Vec<u8> = BASE64_NOPAD
+            .decode(encoded_digest.as_bytes())
+            .map_err(Error::InvalidBase64Encoding)?;
+        Ok(NixHash { digest, algo })
+    } else {
+        // NOTE: As of now, we reject SRI hashes containing additional
+        // characters (which upstream Nix seems to simply truncate), as
+        // there's no occurence of this is in nixpkgs.
+        // It most likely should also be a bug in Nix.
+        Err(Error::InvalidEncodedDigestLength(
+            encoded_digest.as_bytes().len(),
+            algo,
+        ))
+    }
+}
+
+/// decode a plain digest depending on the hash algo specified externally.
+fn decode_digest(s: &str, algo: HashAlgo) -> Result<NixHash, Error> {
+    // for the chosen hash algo, calculate the expected (decoded) digest length
+    // (as bytes)
+    let expected_digest_len = hash_algo_length(&algo);
+
+    Ok(NixHash {
+        digest: match s.len() {
+            n if n == data_encoding::HEXLOWER.encode_len(expected_digest_len) => {
+                data_encoding::HEXLOWER
+                    .decode(s.as_ref())
+                    .map_err(Error::InvalidBase16Encoding)
+            }
+            n if n == nixbase32::encode_len(expected_digest_len) => {
+                nixbase32::decode(s.as_ref()).map_err(Error::InvalidBase32Encoding)
+            }
+            n if n == BASE64.encode_len(expected_digest_len) => BASE64
+                .decode(s.as_ref())
+                .map_err(Error::InvalidBase64Encoding),
+            _ => return Err(Error::InvalidEncodedDigestLength(s.len(), algo)),
+        }?,
+        algo,
+    })
+}
+
+// return the number of bytes in the digest of the given hash algo.
+fn hash_algo_length(hash_algo: &HashAlgo) -> usize {
+    match hash_algo {
+        HashAlgo::Sha1 => 20,
+        HashAlgo::Sha256 => 32,
+        HashAlgo::Sha512 => 64,
+        HashAlgo::Md5 => 16,
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{
+        nixbase32,
+        nixhash::{self, HashAlgo, NixHash},
+    };
+    use test_case::test_case;
+    const DIGEST_SHA1: &[u8] = &[
+        0x60, 0x16, 0x77, 0x79, 0x97, 0xc3, 0x0a, 0xb0, 0x24, 0x13, 0xcf, 0x50, 0x95, 0x62, 0x2c,
+        0xd7, 0x92, 0x42, 0x83, 0xac,
+    ];
+
+    const DIGEST_SHA256: &[u8] = &[
+        0xa5, 0xce, 0x9c, 0x15, 0x5e, 0xd0, 0x93, 0x97, 0x61, 0x46, 0x46, 0xc9, 0x71, 0x7f, 0xc7,
+        0xcd, 0x94, 0xb1, 0x02, 0x3d, 0x7b, 0x76, 0xb6, 0x18, 0xd4, 0x09, 0xe4, 0xfe, 0xfd, 0x6e,
+        0x9d, 0x39,
+    ];
+
+    const DIGEST_SHA512: &[u8] = &[
+        0xab, 0x40, 0xd0, 0xbe, 0x35, 0x41, 0xf0, 0x77, 0x4b, 0xba, 0x78, 0x15, 0xd1, 0x3d, 0x10,
+        0xb0, 0x32, 0x52, 0xe9, 0x6e, 0x95, 0xf7, 0xdb, 0xb4, 0xee, 0x99, 0xa3, 0xb4, 0x31, 0xc2,
+        0x16, 0x62, 0xfd, 0x69, 0x71, 0xa0, 0x20, 0x16, 0x0e, 0x39, 0x84, 0x8a, 0xa5, 0xf3, 0x05,
+        0xb9, 0xbe, 0x0f, 0x78, 0x72, 0x7b, 0x2b, 0x07, 0x89, 0xe3, 0x9f, 0x12, 0x4d, 0x21, 0xe9,
+        0x2b, 0x8f, 0x39, 0xef,
+    ];
+    const DIGEST_MD5: &[u8] = &[
+        0xc4, 0x87, 0x4a, 0x88, 0x97, 0x44, 0x0b, 0x39, 0x3d, 0x86, 0x2d, 0x8f, 0xd4, 0x59, 0x07,
+        0x3f,
+    ];
+
+    fn to_base16(digest: &[u8]) -> String {
+        data_encoding::HEXLOWER.encode(digest)
+    }
+
+    fn to_nixbase32(digest: &[u8]) -> String {
+        nixbase32::encode(digest)
+    }
+
+    fn to_base64(digest: &[u8]) -> String {
+        data_encoding::BASE64.encode(digest)
+    }
+
+    fn to_base64_nopad(digest: &[u8]) -> String {
+        data_encoding::BASE64_NOPAD.encode(digest)
+    }
+
+    // TODO
+    fn make_nixhash(algo: &HashAlgo, digest_encoded: String) -> String {
+        format!("{}:{}", algo, digest_encoded)
+    }
+    fn make_sri_string(algo: &HashAlgo, digest_encoded: String) -> String {
+        format!("{}-{}", algo, digest_encoded)
+    }
+
+    /// Test parsing a hash string in various formats, and also when/how the out-of-band algo is needed.
+    #[test_case(DIGEST_SHA1, HashAlgo::Sha1; "sha1")]
+    #[test_case(DIGEST_SHA256, HashAlgo::Sha256; "sha256")]
+    #[test_case(DIGEST_SHA512, HashAlgo::Sha512; "sha512")]
+    #[test_case(DIGEST_MD5, HashAlgo::Md5; "md5")]
+    fn from_str(digest: &[u8], algo: HashAlgo) {
+        let expected_hash = NixHash {
+            digest: digest.to_vec(),
+            algo: algo.clone(),
+        };
+        // parse SRI
+        {
+            // base64 without out-of-band algo
+            let s = make_sri_string(&algo, to_base64(digest));
+            let h = nixhash::from_str(&s, None).expect("must succeed");
+            assert_eq!(expected_hash, h);
+
+            // base64 with out-of-band-algo
+            let s = make_sri_string(&algo, to_base64(digest));
+            let h = nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed");
+            assert_eq!(expected_hash, h);
+
+            // base64_nopad without out-of-band algo
+            let s = make_sri_string(&algo, to_base64_nopad(digest));
+            let h = nixhash::from_str(&s, None).expect("must succeed");
+            assert_eq!(expected_hash, h);
+
+            // base64_nopad with out-of-band-algo
+            let s = make_sri_string(&algo, to_base64_nopad(digest));
+            let h = nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed");
+            assert_eq!(expected_hash, h);
+        }
+
+        // parse plain base16. should succeed with algo out-of-band, but fail without.
+        {
+            let s = to_base16(digest);
+            nixhash::from_str(&s, None).expect_err("must fail");
+            let h = nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed");
+            assert_eq!(expected_hash, h);
+        }
+
+        // parse plain nixbase32. should succeed with algo out-of-band, but fail without.
+        {
+            let s = to_nixbase32(digest);
+            nixhash::from_str(&s, None).expect_err("must fail");
+            let h = nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed");
+            assert_eq!(expected_hash, h);
+        }
+
+        // parse plain base64. should succeed with algo out-of-band, but fail without.
+        {
+            let s = to_base64(digest);
+            nixhash::from_str(&s, None).expect_err("must fail");
+            let h = nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed");
+            assert_eq!(expected_hash, h);
+        }
+
+        // parse Nix hash strings
+        {
+            // base16. should succeed with both algo out-of-band and in-band.
+            {
+                let s = make_nixhash(&algo, to_base16(digest));
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, None).expect("must succeed")
+                );
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed")
+                );
+            }
+            // nixbase32. should succeed with both algo out-of-band and in-band.
+            {
+                let s = make_nixhash(&algo, to_nixbase32(digest));
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, None).expect("must succeed")
+                );
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed")
+                );
+            }
+            // base64. should succeed with both algo out-of-band and in-band.
+            {
+                let s = make_nixhash(&algo, to_base64(digest));
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, None).expect("must succeed")
+                );
+                assert_eq!(
+                    expected_hash,
+                    nixhash::from_str(&s, Some(&algo.to_string())).expect("must succeed")
+                );
+            }
+        }
+    }
+
+    /// Test parsing an SRI hash via the [nixhash::from_sri_str] method.
+    #[test]
+    fn from_sri_str() {
+        let nix_hash = nixhash::from_sri_str("sha256-pc6cFV7Qk5dhRkbJcX/HzZSxAj17drYY1Ank/v1unTk=")
+            .expect("must succeed");
+
+        assert_eq!(HashAlgo::Sha256, nix_hash.algo);
+        assert_eq!(
+            vec![
+                0xa5, 0xce, 0x9c, 0x15, 0x5e, 0xd0, 0x93, 0x97, 0x61, 0x46, 0x46, 0xc9, 0x71, 0x7f,
+                0xc7, 0xcd, 0x94, 0xb1, 0x02, 0x3d, 0x7b, 0x76, 0xb6, 0x18, 0xd4, 0x09, 0xe4, 0xfe,
+                0xfd, 0x6e, 0x9d, 0x39
+            ],
+            nix_hash.digest
+        )
+    }
+
+    /// Ensure we detect truncated base64 digests, where the digest size
+    /// doesn't match what's expected from that hash function.
+    #[test]
+    fn from_sri_str_truncated() {
+        nixhash::from_sri_str("sha256-pc6cFV7Qk5dhRkbJcX/HzZSxAj17drYY1Ank")
+            .expect_err("must fail");
+    }
+
+    /// Ensure we fail on SRI hashes that Nix doesn't support.
+    #[test]
+    fn from_sri_str_unsupported() {
+        nixhash::from_sri_str(
+            "sha384-o4UVSl89mIB0sFUK+3jQbG+C9Zc9dRlV/Xd3KAvXEbhqxu0J5OAdg6b6VHKHwQ7U",
+        )
+        .expect_err("must fail");
+    }
+
+    /// Ensure we reject invalid base64 encoding
+    #[test]
+    fn from_sri_str_invalid_base64() {
+        nixhash::from_sri_str("sha256-invalid=base64").expect_err("must fail");
+    }
+
+    /// Ensure we reject SRI strings with multiple hashes, as Nix doesn't support that.
+    #[test]
+    fn from_sri_str_unsupported_multiple() {
+        nixhash::from_sri_str("sha256-ngth6szLtC1IJIYyz3lhftzL8SkrJkqPyPve+dGqa1Y= sha512-q0DQvjVB8HdLungV0T0QsDJS6W6V99u07pmjtDHCFmL9aXGgIBYOOYSKpfMFub4PeHJ7KweJ458STSHpK4857w==").expect_err("must fail");
+    }
+
+    /// Nix also accepts SRI strings with missing padding, but only in case the
+    /// string is expressed as SRI, so it still needs to have a `sha256-` prefix.
+    ///
+    /// This both seems to work if it is passed with and without specifying the
+    /// hash algo out-of-band (hash = "sha256-…" or sha256 = "sha256-…")
+    ///
+    /// Passing the same broken base64 string, but not as SRI, while passing
+    /// the hash algo out-of-band does not work.
+    #[test]
+    fn sha256_broken_padding() {
+        let broken_base64 = "fgIr3TyFGDAXP5+qoAaiMKDg/a1MlT6Fv/S/DaA24S8";
+        // if padded with a trailing '='
+        let expected_digest = vec![
+            0x7e, 0x02, 0x2b, 0xdd, 0x3c, 0x85, 0x18, 0x30, 0x17, 0x3f, 0x9f, 0xaa, 0xa0, 0x06,
+            0xa2, 0x30, 0xa0, 0xe0, 0xfd, 0xad, 0x4c, 0x95, 0x3e, 0x85, 0xbf, 0xf4, 0xbf, 0x0d,
+            0xa0, 0x36, 0xe1, 0x2f,
+        ];
+
+        // passing hash algo out of band should succeed
+        let nix_hash = nixhash::from_str(&format!("sha256-{}", &broken_base64), Some("sha256"))
+            .expect("must succeed");
+        assert_eq!(&expected_digest, &nix_hash.digest);
+
+        // not passing hash algo out of band should succeed
+        let nix_hash =
+            nixhash::from_str(&format!("sha256-{}", &broken_base64), None).expect("must succeed");
+        assert_eq!(&expected_digest, &nix_hash.digest);
+
+        // not passing SRI, but hash algo out of band should fail
+        nixhash::from_str(broken_base64, Some("sha256")).expect_err("must fail");
+    }
+}
diff --git a/tvix/nix-compat/src/nixhash/with_mode.rs b/tvix/nix-compat/src/nixhash/with_mode.rs
new file mode 100644
index 000000000000..1908f27b4759
--- /dev/null
+++ b/tvix/nix-compat/src/nixhash/with_mode.rs
@@ -0,0 +1,136 @@
+use crate::nixbase32;
+use crate::nixhash::{HashAlgo, NixHash};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+pub enum NixHashMode {
+    Flat,
+    Recursive,
+}
+
+impl NixHashMode {
+    pub fn prefix(self) -> &'static str {
+        match self {
+            Self::Flat => "",
+            Self::Recursive => "r:",
+        }
+    }
+}
+
+/// A Nix Hash can either be flat or recursive.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum NixHashWithMode {
+    Flat(NixHash),
+    Recursive(NixHash),
+}
+
+impl NixHashWithMode {
+    pub fn mode(&self) -> NixHashMode {
+        match self {
+            Self::Flat(_) => NixHashMode::Flat,
+            Self::Recursive(_) => NixHashMode::Recursive,
+        }
+    }
+
+    pub fn digest(&self) -> &NixHash {
+        match self {
+            Self::Flat(ref h) => h,
+            Self::Recursive(ref h) => h,
+        }
+    }
+
+    /// Formats a [NixHashWithMode] in the Nix default hash format,
+    /// which is the algo, followed by a colon, then the lower hex encoded digest.
+    /// In case the hash itself is recursive, a `r:` is added as prefix
+    pub fn to_nix_hash_string(&self) -> String {
+        String::from(self.mode().prefix()) + &self.digest().to_nix_hash_string()
+    }
+}
+
+impl Serialize for NixHashWithMode {
+    /// map a NixHashWithMode into the serde data model.
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        let mut map = serializer.serialize_map(Some(2))?;
+        match self {
+            NixHashWithMode::Flat(h) => {
+                map.serialize_entry("hash", &nixbase32::encode(&h.digest))?;
+                map.serialize_entry("hashAlgo", &h.algo.to_string())?;
+            }
+            NixHashWithMode::Recursive(h) => {
+                map.serialize_entry("hash", &nixbase32::encode(&h.digest))?;
+                map.serialize_entry("hashAlgo", &format!("r:{}", &h.algo.to_string()))?;
+            }
+        };
+        map.end()
+    }
+}
+
+impl<'de> Deserialize<'de> for NixHashWithMode {
+    /// map the serde data model into a NixHashWithMode.
+    ///
+    /// The serde data model has a `hash` field (containing a digest in nixbase32),
+    /// and a `hashAlgo` field, containing the stringified hash algo.
+    /// In case the hash is recursive, hashAlgo also has a `r:` prefix.
+    ///
+    /// This is to match how `nix show-derivation` command shows them in JSON
+    /// representation.
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        // TODO: don't use serde_json here?
+        // TODO: serde seems to simply set `hash_with_mode` to None if hash
+        // and hashAlgo fail, but that should be a proper deserialization error
+        // that should be propagated to the user!
+
+        let json = serde_json::Value::deserialize(deserializer)?;
+        match json.as_object() {
+            None => Err(serde::de::Error::custom("couldn't parse as map"))?,
+            Some(map) => {
+                let digest: Vec<u8> = {
+                    if let Some(v) = map.get("hash") {
+                        if let Some(s) = v.as_str() {
+                            data_encoding::HEXLOWER
+                                .decode(s.as_bytes())
+                                .map_err(|e| serde::de::Error::custom(e.to_string()))?
+                        } else {
+                            return Err(serde::de::Error::custom(
+                                "couldn't parse 'hash' as string",
+                            ));
+                        }
+                    } else {
+                        return Err(serde::de::Error::custom("couldn't extract 'hash' key"));
+                    }
+                };
+
+                if let Some(v) = map.get("hashAlgo") {
+                    if let Some(s) = v.as_str() {
+                        match s.strip_prefix("r:") {
+                            Some(rest) => Ok(NixHashWithMode::Recursive(NixHash::new(
+                                HashAlgo::try_from(rest).map_err(|e| {
+                                    serde::de::Error::custom(format!("unable to parse algo: {}", e))
+                                })?,
+                                digest,
+                            ))),
+                            None => Ok(NixHashWithMode::Flat(NixHash::new(
+                                HashAlgo::try_from(s).map_err(|e| {
+                                    serde::de::Error::custom(format!("unable to parse algo: {}", e))
+                                })?,
+                                digest,
+                            ))),
+                        }
+                    } else {
+                        Err(serde::de::Error::custom(
+                            "couldn't parse 'hashAlgo' as string",
+                        ))
+                    }
+                } else {
+                    Err(serde::de::Error::custom("couldn't extract 'hashAlgo' key"))
+                }
+            }
+        }
+    }
+}
diff --git a/tvix/nix-compat/src/store_path/mod.rs b/tvix/nix-compat/src/store_path/mod.rs
new file mode 100644
index 000000000000..a67132cb8e30
--- /dev/null
+++ b/tvix/nix-compat/src/store_path/mod.rs
@@ -0,0 +1,294 @@
+use crate::nixbase32::{self, Nixbase32DecodeError};
+use std::{fmt, path::PathBuf};
+use thiserror::Error;
+
+mod utils;
+
+pub use utils::*;
+
+pub const DIGEST_SIZE: usize = 20;
+// lazy_static doesn't allow us to call NIXBASE32.encode_len(), so we ran it
+// manually and have an assert in the tests.
+pub const ENCODED_DIGEST_SIZE: usize = 32;
+
+// The store dir prefix, without trailing slash.
+// That's usually where the Nix store is mounted at.
+pub const STORE_DIR: &str = "/nix/store";
+pub const STORE_DIR_WITH_SLASH: &str = "/nix/store/";
+
+/// Errors that can occur when parsing a literal store path
+#[derive(Debug, PartialEq, Eq, Error)]
+pub enum Error {
+    #[error("Dash is missing between hash and name")]
+    MissingDash(),
+    #[error("Hash encoding is invalid: {0}")]
+    InvalidHashEncoding(Nixbase32DecodeError),
+    #[error("{0}")]
+    InvalidName(NameError),
+    #[error("Tried to parse an absolute path which was missing the store dir prefix.")]
+    MissingStoreDir(),
+}
+
+/// Errors that can occur during the validation of name characters.
+#[derive(Debug, PartialEq, Eq, Error)]
+pub enum NameError {
+    #[error("Invalid name: {0}")]
+    InvalidName(String),
+}
+
+impl From<NameError> for Error {
+    fn from(e: NameError) -> Self {
+        Self::InvalidName(e)
+    }
+}
+
+/// Represents a path in the Nix store (a direct child of [STORE_DIR]).
+///
+/// It consists of a digest (20 bytes), and a name, which is a string.
+/// The name may only contain ASCII alphanumeric, or one of the following
+/// characters: `-`, `_`, `.`, `+`, `?`, `=`.
+/// The name is usually used to describe the pname and version of a package.
+/// Derivation paths can also be represented as store paths, their names just
+/// end with the `.drv` prefix.
+///
+/// A [StorePath] does not encode any additional subpath "inside" the store
+/// path.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct StorePath {
+    pub digest: [u8; DIGEST_SIZE],
+    pub name: String,
+}
+
+impl StorePath {
+    /// Construct a [StorePath] by passing the `$digest-$name` string
+    /// that comes after [STORE_DIR_WITH_SLASH].
+    pub fn from_string(s: &str) -> Result<StorePath, Error> {
+        // the whole string needs to be at least:
+        //
+        // - 32 characters (encoded hash)
+        // - 1 dash
+        // - 1 character for the name
+        if s.len() < ENCODED_DIGEST_SIZE + 2 {
+            Err(NameError::InvalidName("".to_string()))?;
+        }
+
+        let digest = match nixbase32::decode(s[..ENCODED_DIGEST_SIZE].as_bytes()) {
+            Ok(decoded) => decoded,
+            Err(decoder_error) => return Err(Error::InvalidHashEncoding(decoder_error)),
+        };
+
+        if s.as_bytes()[ENCODED_DIGEST_SIZE] != b'-' {
+            return Err(Error::MissingDash());
+        }
+
+        StorePath::validate_name(&s[ENCODED_DIGEST_SIZE + 2..])?;
+
+        Ok(StorePath {
+            name: s[ENCODED_DIGEST_SIZE + 1..].to_string(),
+            digest: digest.try_into().expect("size is known"),
+        })
+    }
+
+    /// Construct a [StorePath] from an absolute store path string.
+    /// This is equivalent to calling [StorePath::from_string], but stripping
+    /// the [STORE_DIR_WITH_SLASH] prefix before.
+    pub fn from_absolute_path(s: &str) -> Result<StorePath, Error> {
+        match s.strip_prefix(STORE_DIR_WITH_SLASH) {
+            Some(s_stripped) => Self::from_string(s_stripped),
+            None => Err(Error::MissingStoreDir()),
+        }
+    }
+
+    /// Decompose a string into a [StorePath] and a [PathBuf] containing the
+    /// rest of the path, or an error.
+    pub fn from_absolute_path_full(s: &str) -> Result<(StorePath, PathBuf), Error> {
+        // strip [STORE_DIR_WITH_SLASH] from s
+        match s.strip_prefix(STORE_DIR_WITH_SLASH) {
+            None => Err(Error::MissingStoreDir()),
+            Some(rest) => {
+                // put rest in a PathBuf
+                let mut p = PathBuf::new();
+                p.push(rest);
+
+                let mut it = p.components();
+
+                // The first component of the rest must be parse-able as a [StorePath]
+                if let Some(s) = it.next() {
+                    // convert first component to string
+                    if let Some(s) = s.as_os_str().to_str() {
+                        let store_path = StorePath::from_string(s)?;
+                        let rest_buf: PathBuf = it.collect();
+                        Ok((store_path, rest_buf))
+                    } else {
+                        Err(Error::InvalidName(NameError::InvalidName("".to_string())))
+                    }
+                } else {
+                    Err(Error::InvalidName(NameError::InvalidName("".to_string())))
+                }
+            }
+        }
+    }
+
+    /// Converts the [StorePath] to an absolute store path string.
+    /// That is just the string representation, prefixed with the store prefix
+    /// ([STORE_DIR_WITH_SLASH]),
+    pub fn to_absolute_path(&self) -> String {
+        format!("{}{}", STORE_DIR_WITH_SLASH, self)
+    }
+
+    /// Checks a given &str to match the restrictions for store path names.
+    pub fn validate_name(s: &str) -> Result<(), NameError> {
+        for c in s.chars() {
+            if c.is_ascii_alphanumeric()
+                || c == '-'
+                || c == '_'
+                || c == '.'
+                || c == '+'
+                || c == '?'
+                || c == '='
+            {
+                continue;
+            }
+
+            return Err(NameError::InvalidName(s.to_string()));
+        }
+
+        Ok(())
+    }
+}
+
+impl fmt::Display for StorePath {
+    /// The string representation of a store path starts with a digest (20
+    /// bytes), [crate::nixbase32]-encoded, followed by a `-`,
+    /// and ends with the name.
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{}-{}", nixbase32::encode(&self.digest), self.name)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::path::PathBuf;
+
+    use crate::nixbase32;
+    use crate::store_path::{DIGEST_SIZE, ENCODED_DIGEST_SIZE};
+    use test_case::test_case;
+
+    use super::{Error, NameError, StorePath};
+
+    #[test]
+    fn encoded_digest_size() {
+        assert_eq!(ENCODED_DIGEST_SIZE, nixbase32::encode_len(DIGEST_SIZE));
+    }
+
+    #[test]
+    fn happy_path() {
+        let example_nix_path_str =
+            "00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432";
+        let nixpath =
+            StorePath::from_string(example_nix_path_str).expect("Error parsing example string");
+
+        let expected_digest: [u8; DIGEST_SIZE] = [
+            0x8a, 0x12, 0x32, 0x15, 0x22, 0xfd, 0x91, 0xef, 0xbd, 0x60, 0xeb, 0xb2, 0x48, 0x1a,
+            0xf8, 0x85, 0x80, 0xf6, 0x16, 0x00,
+        ];
+
+        assert_eq!("net-tools-1.60_p20170221182432", nixpath.name);
+        assert_eq!(nixpath.digest, expected_digest);
+
+        assert_eq!(example_nix_path_str, nixpath.to_string())
+    }
+
+    #[test]
+    fn invalid_hash_length() {
+        StorePath::from_string("00bgd045z0d4icpbc2yy-net-tools-1.60_p20170221182432")
+            .expect_err("must fail");
+    }
+
+    #[test]
+    fn invalid_encoding_hash() {
+        StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48aku4la-net-tools-1.60_p20170221182432")
+            .expect_err("must fail");
+    }
+
+    #[test]
+    fn more_than_just_the_bare_nix_store_path() {
+        StorePath::from_string(
+            "00bgd045z0d4icpbc2yyz4gx48aku4la-net-tools-1.60_p20170221182432/bin/arp",
+        )
+        .expect_err("must fail");
+    }
+
+    #[test]
+    fn no_dash_between_hash_and_name() {
+        StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48ak44lanet-tools-1.60_p20170221182432")
+            .expect_err("must fail");
+    }
+
+    #[test]
+    fn absolute_path() {
+        let example_nix_path_str =
+            "00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432";
+        let nixpath_expected = StorePath::from_string(example_nix_path_str).expect("must parse");
+
+        let nixpath_actual = StorePath::from_absolute_path(
+            "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432",
+        )
+        .expect("must parse");
+
+        assert_eq!(nixpath_expected, nixpath_actual);
+
+        assert_eq!(
+            "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432",
+            nixpath_actual.to_absolute_path(),
+        );
+    }
+
+    #[test]
+    fn absolute_path_missing_prefix() {
+        assert_eq!(
+            Error::MissingStoreDir(),
+            StorePath::from_absolute_path("foobar-123").expect_err("must fail")
+        );
+    }
+
+    #[test_case(
+        "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432",
+        (StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432").unwrap(), PathBuf::new())
+    ; "without prefix")]
+    #[test_case(
+        "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432/",
+        (StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432").unwrap(), PathBuf::new())
+    ; "without prefix, but trailing slash")]
+    #[test_case(
+        "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432/bin/arp",
+        (StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432").unwrap(), PathBuf::from("bin/arp"))
+    ; "with prefix")]
+    #[test_case(
+        "/nix/store/00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432/bin/arp/",
+        (StorePath::from_string("00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432").unwrap(), PathBuf::from("bin/arp/"))
+    ; "with prefix and trailing slash")]
+    fn from_absolute_path_full(s: &str, expected: (StorePath, PathBuf)) {
+        let actual = StorePath::from_absolute_path_full(s).expect("must succeed");
+        assert_eq!(expected, actual);
+    }
+
+    #[test]
+    fn from_absolute_path_errors() {
+        assert_eq!(
+            Error::InvalidName(NameError::InvalidName("".to_string())),
+            StorePath::from_absolute_path_full("/nix/store/").expect_err("must fail")
+        );
+        assert_eq!(
+            Error::InvalidName(NameError::InvalidName("".to_string())),
+            StorePath::from_absolute_path_full("/nix/store/foo").expect_err("must fail")
+        );
+        assert_eq!(
+            Error::MissingStoreDir(),
+            StorePath::from_absolute_path_full(
+                "00bgd045z0d4icpbc2yyz4gx48ak44la-net-tools-1.60_p20170221182432"
+            )
+            .expect_err("must fail")
+        );
+    }
+}
diff --git a/tvix/nix-compat/src/store_path/utils.rs b/tvix/nix-compat/src/store_path/utils.rs
new file mode 100644
index 000000000000..fd3785568bac
--- /dev/null
+++ b/tvix/nix-compat/src/store_path/utils.rs
@@ -0,0 +1,289 @@
+use crate::nixbase32;
+use crate::nixhash::{HashAlgo, NixHash, NixHashWithMode};
+use crate::store_path::StorePath;
+use sha2::{Digest, Sha256};
+use thiserror::Error;
+
+use super::{NameError, STORE_DIR};
+
+/// Errors that can occur when creating a content-addressed store path.
+///
+/// This wraps the main [Error] which is just about invalid store path names.
+#[derive(Debug, PartialEq, Eq, Error)]
+pub enum BuildStorePathError {
+    #[error("{0}")]
+    InvalidName(NameError),
+    /// This error occurs when we have references outside the SHA-256 +
+    /// Recursive case. The restriction comes from upstream Nix. It may be
+    /// lifted at some point but there isn't a pressing need to anticipate that.
+    #[error("References were not supported as much as requested")]
+    InvalidReference(),
+}
+
+/// compress_hash takes an arbitrarily long sequence of bytes (usually
+/// a hash digest), and returns a sequence of bytes of length
+/// OUTPUT_SIZE.
+///
+/// It's calculated by rotating through the bytes in the output buffer
+/// (zero- initialized), and XOR'ing with each byte of the passed
+/// input. It consumes 1 byte at a time, and XOR's it with the current
+/// value in the output buffer.
+///
+/// This mimics equivalent functionality in C++ Nix.
+pub fn compress_hash<const OUTPUT_SIZE: usize>(input: &[u8]) -> [u8; OUTPUT_SIZE] {
+    let mut output = [0; OUTPUT_SIZE];
+
+    for (ii, ch) in input.iter().enumerate() {
+        output[ii % OUTPUT_SIZE] ^= ch;
+    }
+
+    output
+}
+
+/// This builds a store path, by calculating the text_hash_string of either a
+/// derivation or a literal text file that may contain references.
+pub fn build_text_path<S: AsRef<str>, I: IntoIterator<Item = S>, C: AsRef<[u8]>>(
+    name: &str,
+    content: C,
+    references: I,
+) -> Result<StorePath, NameError> {
+    build_store_path_from_fingerprint_parts(
+        &make_type("text", references, false),
+        // the nix_hash_string representation of the sha256 digest of some contents
+        &{
+            let content_digest = {
+                let hasher = Sha256::new_with_prefix(content);
+                hasher.finalize()
+            };
+            NixHash::new(crate::nixhash::HashAlgo::Sha256, content_digest.to_vec())
+        },
+        name,
+    )
+}
+
+/// This builds a more "regular" content-addressed store path
+pub fn build_regular_ca_path<S: AsRef<str>, I: IntoIterator<Item = S>>(
+    name: &str,
+    hash_with_mode: &NixHashWithMode,
+    references: I,
+    self_reference: bool,
+) -> Result<StorePath, BuildStorePathError> {
+    match &hash_with_mode {
+        NixHashWithMode::Recursive(
+            ref hash @ NixHash {
+                algo: HashAlgo::Sha256,
+                ..
+            },
+        ) => build_store_path_from_fingerprint_parts(
+            &make_type("source", references, self_reference),
+            hash,
+            name,
+        )
+        .map_err(BuildStorePathError::InvalidName),
+        _ => {
+            if references.into_iter().next().is_some() {
+                return Err(BuildStorePathError::InvalidReference());
+            }
+            if self_reference {
+                return Err(BuildStorePathError::InvalidReference());
+            }
+            build_store_path_from_fingerprint_parts(
+                "output:out",
+                &{
+                    let content_digest = {
+                        let mut hasher = Sha256::new_with_prefix("fixed:out:");
+                        hasher.update(hash_with_mode.mode().prefix());
+                        hasher.update(hash_with_mode.digest().algo.to_string());
+                        hasher.update(":");
+                        hasher.update(
+                            &data_encoding::HEXLOWER.encode(&hash_with_mode.digest().digest),
+                        );
+                        hasher.update(":");
+                        hasher.finalize()
+                    };
+                    NixHash::new(crate::nixhash::HashAlgo::Sha256, content_digest.to_vec())
+                },
+                name,
+            )
+            .map_err(BuildStorePathError::InvalidName)
+        }
+    }
+}
+
+/// This builds an input-addressed store path
+///
+/// Input-addresed store paths are always derivation outputs, the "input" in question is the
+/// derivation and its closure.
+pub fn build_output_path(
+    drv_hash: &NixHash,
+    output_name: &str,
+    output_path_name: &str,
+) -> Result<StorePath, NameError> {
+    build_store_path_from_fingerprint_parts(
+        &(String::from("output:") + output_name),
+        drv_hash,
+        output_path_name,
+    )
+}
+
+/// This builds a store path from fingerprint parts.
+/// Usually, that function is used from [build_text_path] and
+/// passed a "text hash string" (starting with "text:" as fingerprint),
+/// but other fingerprints starting with "output:" are also used in Derivation
+/// output path calculation.
+///
+/// The fingerprint is hashed with sha256, its digest is compressed to 20 bytes,
+/// and nixbase32-encoded (32 characters).
+fn build_store_path_from_fingerprint_parts(
+    ty: &str,
+    hash: &NixHash,
+    name: &str,
+) -> Result<StorePath, NameError> {
+    let fingerprint =
+        String::from(ty) + ":" + &hash.to_nix_hash_string() + ":" + STORE_DIR + ":" + name;
+    let digest = {
+        let hasher = Sha256::new_with_prefix(fingerprint);
+        hasher.finalize()
+    };
+    let compressed = compress_hash::<20>(&digest);
+    StorePath::validate_name(name)?;
+    Ok(StorePath {
+        digest: compressed,
+        name: name.to_string(),
+    })
+}
+
+/// This contains the Nix logic to create "text hash strings", which are used
+/// in `builtins.toFile`, as well as in Derivation Path calculation.
+///
+/// A text hash is calculated by concatenating the following fields, separated by a `:`:
+///
+///  - text
+///  - references, individually joined by `:`
+///  - the nix_hash_string representation of the sha256 digest of some contents
+///  - the value of `storeDir`
+///  - the name
+fn make_type<S: AsRef<str>, I: IntoIterator<Item = S>>(
+    ty: &str,
+    references: I,
+    self_ref: bool,
+) -> String {
+    let mut s = String::from(ty);
+
+    for reference in references {
+        s.push(':');
+        s.push_str(reference.as_ref());
+    }
+
+    if self_ref {
+        s.push_str(":self");
+    }
+
+    s
+}
+
+/// Nix placeholders (i.e. values returned by `builtins.placeholder`)
+/// are used to populate outputs with paths that must be
+/// string-replaced with the actual placeholders later, at runtime.
+///
+/// The actual placeholder is basically just a SHA256 hash encoded in
+/// cppnix format.
+pub fn hash_placeholder(name: &str) -> String {
+    let digest = {
+        let mut hasher = Sha256::new();
+        hasher.update(format!("nix-output:{}", name));
+        hasher.finalize()
+    };
+
+    format!("/{}", nixbase32::encode(&digest))
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use crate::nixhash::{NixHash, NixHashWithMode};
+
+    #[test]
+    fn build_text_path_with_zero_references() {
+        // This hash should match `builtins.toFile`, e.g.:
+        //
+        // nix-repl> builtins.toFile "foo" "bar"
+        // "/nix/store/vxjiwkjkn7x4079qvh1jkl5pn05j2aw0-foo"
+
+        let store_path = build_text_path("foo", "bar", Vec::<String>::new())
+            .expect("build_store_path() should succeed");
+
+        assert_eq!(
+            store_path.to_absolute_path().as_str(),
+            "/nix/store/vxjiwkjkn7x4079qvh1jkl5pn05j2aw0-foo"
+        );
+    }
+
+    #[test]
+    fn build_text_path_with_non_zero_references() {
+        // This hash should match:
+        //
+        // nix-repl> builtins.toFile "baz" "${builtins.toFile "foo" "bar"}"
+        // "/nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz"
+
+        let inner = build_text_path("foo", "bar", Vec::<String>::new())
+            .expect("path_with_references() should succeed");
+        let inner_path = inner.to_absolute_path();
+
+        let outer = build_text_path("baz", &inner_path, vec![inner_path.as_str()])
+            .expect("path_with_references() should succeed");
+
+        assert_eq!(
+            outer.to_absolute_path().as_str(),
+            "/nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz"
+        );
+    }
+
+    #[test]
+    fn build_sha1_path() {
+        let outer = build_regular_ca_path(
+            "bar",
+            &NixHashWithMode::Recursive(NixHash {
+                algo: HashAlgo::Sha1,
+                digest: data_encoding::HEXLOWER
+                    .decode(b"0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33")
+                    .expect("hex should decode"),
+            }),
+            Vec::<String>::new(),
+            false,
+        )
+        .expect("path_with_references() should succeed");
+
+        assert_eq!(
+            outer.to_absolute_path().as_str(),
+            "/nix/store/mp57d33657rf34lzvlbpfa1gjfv5gmpg-bar"
+        );
+    }
+
+    #[test]
+    fn build_store_path_with_non_zero_references() {
+        // This hash should match:
+        //
+        // nix-repl> builtins.toFile "baz" "${builtins.toFile "foo" "bar"}"
+        // "/nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz"
+        //
+        // $ nix store make-content-addressed /nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz
+        // rewrote '/nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz' to '/nix/store/s89y431zzhmdn3k8r96rvakryddkpv2v-baz'
+        let outer = build_regular_ca_path(
+            "baz",
+            &NixHashWithMode::Recursive(NixHash {
+                algo: HashAlgo::Sha256,
+                digest: nixbase32::decode(b"1xqkzcb3909fp07qngljr4wcdnrh1gdam1m2n29i6hhrxlmkgkv1")
+                    .expect("hex should decode"),
+            }),
+            vec!["/nix/store/dxwkwjzdaq7ka55pkk252gh32bgpmql4-foo"],
+            false,
+        )
+        .expect("path_with_references() should succeed");
+
+        assert_eq!(
+            outer.to_absolute_path().as_str(),
+            "/nix/store/s89y431zzhmdn3k8r96rvakryddkpv2v-baz"
+        );
+    }
+}