refactor(tvix/nix-compat): absorb //tvix/derivation r/5791

Put this in its src/derivation.

Change-Id: Ic047ab1c2da555a833ee454e10ef60c77537b617
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7967
Reviewed-by: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI
Autosubmit: flokli <flokli@flokli.de>

25 files changed, 1322 insertions, 0 deletions

diff --git a/tvix/nix-compat/src/derivation/derivation.rs b/tvix/nix-compat/src/derivation/derivation.rs
new file mode 100644
index 000000000000..c9a45d9c9bd2
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/derivation.rs
@@ -0,0 +1,347 @@
+use crate::derivation::output::{Hash, Output};
+use crate::derivation::write;
+use crate::derivation::DerivationError;
+use crate::nixbase32;
+use crate::store_path::{StorePath, STORE_DIR};
+use serde::{Deserialize, Serialize};
+use sha2::{Digest, Sha256};
+use std::collections::BTreeSet;
+use std::{collections::BTreeMap, fmt, fmt::Write};
+
+#[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,
+}
+
+/// 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.
+fn compress_hash(input: &[u8], output_size: usize) -> Vec<u8> {
+    let mut output: Vec<u8> = vec![0; output_size];
+
+    for (ii, ch) in input.iter().enumerate() {
+        output[ii % output_size] ^= ch;
+    }
+
+    output
+}
+
+/// This returns a store path, either of a derivation or a regular output.
+/// The string is hashed with sha256, its digest is compressed to 20 bytes, and
+/// nixbase32-encoded (32 characters)
+fn build_store_path(
+    is_derivation: bool,
+    fingerprint: &str,
+    name: &str,
+) -> Result<StorePath, DerivationError> {
+    let digest = {
+        let mut hasher = Sha256::new();
+        hasher.update(fingerprint);
+        hasher.finalize()
+    };
+    let compressed = compress_hash(&digest, 20);
+    if is_derivation {
+        StorePath::from_string(format!("{}-{}.drv", nixbase32::encode(&compressed), name).as_str())
+    } else {
+        StorePath::from_string(format!("{}-{}", nixbase32::encode(&compressed), name,).as_str())
+    }
+    .map_err(|_e| DerivationError::InvalidOutputName(name.to_string()))
+    // Constructing the StorePath can only fail if the passed output name was
+    // invalid, so map errors to a [DerivationError::InvalidOutputName].
+}
+
+/// Build a store path for a literal text file in the store that may
+/// contain references.
+pub fn path_with_references<S: AsRef<str>, I: IntoIterator<Item = S>, C: AsRef<[u8]>>(
+    name: &str,
+    content: C,
+    references: I,
+) -> Result<StorePath, DerivationError> {
+    let mut s = String::from("text");
+
+    for reference in references {
+        s.push(':');
+        s.push_str(reference.as_ref());
+    }
+
+    let content_digest = {
+        let mut hasher = Sha256::new();
+        hasher.update(content);
+        hasher.finalize()
+    };
+
+    s.push_str(&format!(
+        ":sha256:{:x}:{}:{}",
+        content_digest, STORE_DIR, name
+    ));
+
+    build_store_path(false, &s, name)
+}
+
+impl Derivation {
+    pub fn serialize(&self, writer: &mut impl Write) -> Result<(), 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(())
+    }
+
+    /// Returns the fixed output path and its hash
+    // (if the Derivation is fixed output),
+    /// or None if there is no fixed output.
+    /// This takes some shortcuts in case more than one output exists, as this
+    /// can't be a valid fixed-output Derivation.
+    pub fn get_fixed_output(&self) -> Option<(&String, &Hash)> {
+        if self.outputs.len() != 1 {
+            return None;
+        }
+
+        match self.outputs.get("out") {
+            #[allow(clippy::manual_map)]
+            Some(out_output) => match &out_output.hash {
+                Some(out_output_hash) => Some((&out_output.path, out_output_hash)),
+                // There has to be a hash, otherwise it would not be FOD
+                None => None,
+            },
+            None => None,
+        }
+    }
+
+    /// Returns the drv path of a Derivation struct.
+    ///
+    /// The drv path is calculated like this:
+    ///   - Write the fingerprint of the Derivation to the sha256 hash function.
+    ///     This is: `text:`,
+    ///     all d.InputDerivations and d.InputSources (sorted, separated by a `:`),
+    ///     a `:`,
+    ///     a `sha256:`, followed by the sha256 digest of the ATerm representation (hex-encoded)
+    ///     a `:`,
+    ///     the storeDir, followed by a `:`,
+    ///     the name of a derivation,
+    ///     a `.drv`.
+    ///   - Write the .drv A-Term contents to a hash function
+    ///   - Take the digest, run hash.CompressHash(digest, 20) on it.
+    ///   - Encode it with nixbase32
+    ///   - Use it (and the name) to construct a [StorePath].
+    pub fn calculate_derivation_path(&self, name: &str) -> Result<StorePath, DerivationError> {
+        let mut s = String::from("text:");
+
+        // collect the list of paths from input_sources and input_derivations
+        // into a (sorted, guaranteed by BTreeSet) list, and join them by :
+        let concat_inputs: 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
+        };
+
+        for input in concat_inputs {
+            s.push_str(&input);
+            s.push(':');
+        }
+
+        // calculate the sha256 hash of the ATerm representation, and represent
+        // it as a hex-encoded string (prefixed with sha256:).
+        let aterm_digest = {
+            let mut derivation_hasher = Sha256::new();
+            derivation_hasher.update(self.to_string());
+            derivation_hasher.finalize()
+        };
+
+        s.push_str(&format!(
+            "sha256:{:x}:{}:{}.drv",
+            aterm_digest, STORE_DIR, name,
+        ));
+
+        build_store_path(true, &s, name)
+    }
+
+    /// Calculate the drv replacement string for a given derivation.
+    ///
+    /// This is either called on a struct without output paths populated,
+    /// to provide the `drv_replacement_str` value for the `calculate_output_paths`
+    /// function call, or called on a struct with output paths populated, to
+    /// calculate / cache lookups for calls to fn_get_drv_replacement.
+    ///
+    /// `fn_get_drv_replacement` is used to look up the drv replacement strings
+    /// for input_derivations the Derivation refers to.
+    pub fn calculate_drv_replacement_str<F>(&self, fn_get_drv_replacement: F) -> String
+    where
+        F: Fn(&str) -> String,
+    {
+        let mut hasher = Sha256::new();
+        let digest = match self.get_fixed_output() {
+            Some((fixed_output_path, fixed_output_hash)) => {
+                hasher.update(format!(
+                    "fixed:out:{}:{}:{}",
+                    &fixed_output_hash.algo, &fixed_output_hash.digest, fixed_output_path,
+                ));
+                hasher.finalize()
+            }
+            None => {
+                let mut replaced_input_derivations: BTreeMap<String, BTreeSet<String>> =
+                    BTreeMap::new();
+
+                // For each input_derivation, look up the replacement.
+                for (drv_path, input_derivation) in &self.input_derivations {
+                    replaced_input_derivations.insert(
+                        fn_get_drv_replacement(drv_path).to_string(),
+                        input_derivation.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
+                hasher.update(replaced_derivation.to_string());
+
+                hasher.finalize()
+            }
+        };
+
+        format!("{:x}", digest)
+    }
+
+    /// 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 "drv replacement
+    /// strings", and in case of non-fixed-output derivations, also knowledge
+    /// of "drv replacement" strings (recursively) of all input derivations.
+    ///
+    /// We solve this by asking the caller of this function to provide
+    /// the drv replacement string of the current derivation itself,
+    /// which is ran on the struct without output paths.
+    ///
+    /// This sound terribly ugly, but won't be too much of a concern later on, as
+    /// naming fixed-output paths once uploaded will be a tvix-store concern,
+    /// so there's no need to calculate them here anymore.
+    ///
+    /// 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,
+        drv_replacement_str: &str,
+    ) -> Result<(), DerivationError> {
+        // Check if the Derivation is fixed output, because they cause
+        // different fingerprints to be hashed.
+        match self.get_fixed_output() {
+            None => {
+                // 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());
+
+                    // calculate the output_name_path, which is the part of the NixPath after the digest.
+                    let mut output_path_name = name.to_string();
+                    if output_name != "out" {
+                        output_path_name.push('-');
+                        output_path_name.push_str(output_name);
+                    }
+
+                    let s = &format!(
+                        "output:{}:sha256:{}:{}:{}",
+                        output_name, drv_replacement_str, STORE_DIR, output_path_name,
+                    );
+
+                    let abs_store_path =
+                        build_store_path(false, s, &output_path_name)?.to_absolute_path();
+
+                    output.path = abs_store_path.clone();
+                    self.environment
+                        .insert(output_name.to_string(), abs_store_path);
+                }
+            }
+            Some((fixed_output_path, fixed_output_hash)) => {
+                // 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!(fixed_output_path.is_empty());
+
+                let s = {
+                    let mut s = String::new();
+                    // Fixed-output derivation.
+                    // There's two different hashing strategies in place, depending on the value of hash.algo.
+                    // This code is _weird_ but it is what Nix is doing. See:
+                    // https://github.com/NixOS/nix/blob/1385b2007804c8a0370f2a6555045a00e34b07c7/src/libstore/store-api.cc#L178-L196
+                    if fixed_output_hash.algo == "r:sha256" {
+                        s.push_str(&format!(
+                            "source:sha256:{}",
+                            fixed_output_hash.digest, // nixbase32
+                        ));
+                    } else {
+                        s.push_str("output:out:sha256:");
+                        // This is drv_replacement for FOD, with an empty fixed_output_path.
+                        s.push_str(drv_replacement_str);
+                    }
+                    s.push_str(&format!(":{}:{}", STORE_DIR, name));
+                    s
+                };
+
+                let abs_store_path = build_store_path(false, &s, name)?.to_absolute_path();
+
+                self.outputs.insert(
+                    "out".to_string(),
+                    Output {
+                        path: abs_store_path.clone(),
+                        hash: Some(fixed_output_hash.clone()),
+                    },
+                );
+                self.environment.insert("out".to_string(), abs_store_path);
+            }
+        };
+
+        Ok(())
+    }
+}
+
+impl fmt::Display for Derivation {
+    /// Formats the Derivation in ATerm representation.
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.serialize(f)
+    }
+}
diff --git a/tvix/nix-compat/src/derivation/errors.rs b/tvix/nix-compat/src/derivation/errors.rs
new file mode 100644
index 000000000000..0dcad9a5345e
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/errors.rs
@@ -0,0 +1,56 @@
+use crate::{nixbase32::Nixbase32DecodeError, store_path::ParseStorePathError};
+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),
+    // input derivation
+    #[error("unable to parse input derivation path {0}: {1}")]
+    InvalidInputDerivationPath(String, ParseStorePathError),
+    #[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, ParseStorePathError),
+
+    // 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 [Output] of a [Derviation].
+#[derive(Debug, Error, PartialEq)]
+pub enum OutputError {
+    #[error("Invalid ouput path {0}: {1}")]
+    InvalidOutputPath(String, ParseStorePathError),
+    #[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..1b82251bf672
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/mod.rs
@@ -0,0 +1,15 @@
+mod derivation;
+mod errors;
+mod output;
+mod string_escape;
+mod validate;
+mod write;
+
+#[cfg(test)]
+mod tests;
+
+// Public API of the crate.
+
+pub use derivation::{path_with_references, Derivation};
+pub use errors::{DerivationError, OutputError};
+pub use output::{Hash, Output};
diff --git a/tvix/nix-compat/src/derivation/output.rs b/tvix/nix-compat/src/derivation/output.rs
new file mode 100644
index 000000000000..9aef7172aec6
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/output.rs
@@ -0,0 +1,54 @@
+use crate::derivation::OutputError;
+use crate::{nixbase32, 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: Option<Hash>,
+}
+
+#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
+pub struct Hash {
+    #[serde(rename = "hash")]
+    pub digest: String,
+    #[serde(rename = "hashAlgo")]
+    pub algo: String,
+}
+
+impl Output {
+    pub fn is_fixed(&self) -> bool {
+        self.hash.is_some()
+    }
+
+    pub fn validate(&self, validate_output_paths: bool) -> Result<(), OutputError> {
+        if let Some(hash) = &self.hash {
+            // try to decode digest
+            let result = nixbase32::decode(&hash.digest.as_bytes());
+            match result {
+                Err(e) => return Err(OutputError::InvalidHashEncoding(hash.digest.clone(), e)),
+                Ok(digest) => {
+                    if hash.algo != "sha1" && hash.algo != "sha256" {
+                        return Err(OutputError::InvalidHashAlgo(hash.algo.to_string()));
+                    }
+                    if (hash.algo == "sha1" && digest.len() != 20)
+                        || (hash.algo == "sha256" && digest.len() != 32)
+                    {
+                        return Err(OutputError::InvalidDigestSizeForAlgo(
+                            digest.len(),
+                            hash.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..57c08f5a75f3
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/tests/mod.rs
@@ -0,0 +1,344 @@
+use crate::derivation::output::{Hash, Output};
+use crate::derivation::Derivation;
+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();
+
+    return 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_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_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 outputs from a Derivation struct,
+/// by setting outputs[$outputName].path and environment[$outputName] to the empty string.
+fn derivation_with_trimmed_outputs(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", "724f3e3634fce4cbbbd3483287b8798588e80280660b9a63fd13a1bc90485b33"; "fixed_sha256")]
+#[test_case("ss2p4wmxijn652haqyd7dckxwl4c7hxx-bar.drv", "c79aebd0ce3269393d4a1fde2cbd1d975d879b40f0bf40a48f550edc107fd5df";"fixed-sha1")]
+fn replacement_drv_path(drv_path: &str, expected_replacement_str: &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 drv_replacement_str = drv.calculate_drv_replacement_str(|_| panic!("must not be called"));
+
+    assert_eq!(expected_replacement_str, drv_replacement_str);
+}
+
+#[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_outputs(&expected_derivation);
+
+    // calculate the drv replacement string.
+    // We don't expect the lookup function to be called for most derivations.
+    let replacement_str = derivation.calculate_drv_replacement_str(|drv_name| {
+        // 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"
+                && drv_name == "/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv")
+                || (drv_path == "ch49594n9avinrf8ip0aslidkc4lxkqv-foo.drv"
+                    && drv_name == "/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(drv_name).file_name().unwrap().to_string_lossy()
+            ));
+
+            let drv: Derivation = serde_json::from_str(&data).expect("must deserialize");
+
+            // calculate replacement string. These don't trigger any subsequent requests, as they're both FOD.
+            drv.calculate_drv_replacement_str(|_| 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");
+        }
+    });
+
+    // We need to calculate the replacement_str, as fixed-sha1 does use it.
+    derivation
+        .calculate_output_paths(&name, &replacement_str)
+        .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: Some(Hash {
+                digest: "08813cbee9903c62be4c5027726a418a300da4500b2d369d3af9286f4815ceba"
+                    .to_string(),
+                algo: "r:sha256".to_string(),
+            }),
+        },
+    );
+
+    // calculate bar output paths
+    let bar_calc_result = bar_drv.calculate_output_paths(
+        "bar",
+        &bar_drv.calculate_drv_replacement_str(|_| 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_replacement_str =
+        &bar_drv.calculate_drv_replacement_str(|_| 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: 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.calculate_drv_replacement_str(|drv_name| {
+            if drv_name != "/nix/store/0hm2f1psjpcwg8fijsmr4wwxrx59s092-bar.drv" {
+                panic!("lookup called with unexpected drv_name: {}", drv_name);
+            }
+            bar_drv_replacement_str.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")
+    );
+}
+
+#[test]
+fn 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 = crate::derivation::path_with_references("foo", "bar", Vec::<String>::new())
+        .expect("path_with_references() should succeed");
+
+    assert_eq!(
+        store_path.to_absolute_path().as_str(),
+        "/nix/store/vxjiwkjkn7x4079qvh1jkl5pn05j2aw0-foo"
+    );
+}
+
+#[test]
+fn path_with_non_zero_references() {
+    // This hash should match:
+    //
+    // nix-repl> builtins.toFile "baz" "${builtins.toFile "foo" "bar"}"
+    // "/nix/store/5xd714cbfnkz02h2vbsj4fm03x3f15nf-baz"
+
+    let inner = crate::derivation::path_with_references("foo", "bar", Vec::<String>::new())
+        .expect("path_with_references() should succeed");
+    let inner_path = inner.to_absolute_path();
+
+    let outer =
+        crate::derivation::path_with_references("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"
+    );
+}
diff --git a/tvix/nix-compat/src/derivation/validate.rs b/tvix/nix-compat/src/derivation/validate.rs
new file mode 100644
index 000000000000..7456f930d15e
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/validate.rs
@@ -0,0 +1,127 @@
+use crate::derivation::{Derivation, DerivationError};
+use crate::store_path::StorePath;
+
+impl Derivation {
+    /// validate ensures a Derivation struct is properly populated,
+    /// and returns a [ValidateDerivationError] 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..9423ef2e6af4
--- /dev/null
+++ b/tvix/nix-compat/src/derivation/write.rs
@@ -0,0 +1,184 @@
+//! 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];
+
+        match &output.hash {
+            Some(hash) => {
+                elements.push(&hash.algo);
+                elements.push(&hash.digest);
+            }
+            None => {
+                elements.push("");
+                elements.push("");
+            }
+        }
+
+        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
index 6ca48e9ef035..59d687ee7fe2 100644
--- a/tvix/nix-compat/src/lib.rs
+++ b/tvix/nix-compat/src/lib.rs
@@ -1,2 +1,3 @@
+pub mod derivation;
 pub mod nixbase32;
 pub mod store_path;