refactor(tvix/derivation): use BTreeSet for derivation outputs r/5657

When constructing derivations inside builtins.derivationStrict, we'd
have to very frequently check whether certain outputs have already
been inserted into the derivation inputs.

Using a set type is much easier, especially as this has to be ordered
and the source data that is being inserted also comes from a set,
which might let us pass this more efficiently in the future.

Note that the validate function no longer checks the order of the
entries, as that is now guaranteed by the type.

Change-Id: I2fbb984facba3e668075f6f8df8992092368c63d
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7826
Tested-by: BuildkiteCI
Reviewed-by: flokli <flokli@flokli.de>

1 files changed, 5 insertions, 3 deletions

diff --git a/tvix/derivation/src/derivation.rs b/tvix/derivation/src/derivation.rs
index 54e0bbf82ec2..d1f46de8c5ee 100644
--- a/tvix/derivation/src/derivation.rs
+++ b/tvix/derivation/src/derivation.rs
@@ -3,6 +3,7 @@ use crate::output::{Hash, Output};
 use crate::write;
 use serde::{Deserialize, Serialize};
 use sha2::{Digest, Sha256};
+use std::collections::BTreeSet;
 use std::{collections::BTreeMap, fmt, fmt::Write};
 use tvix_store::nixbase32::NIXBASE32;
 use tvix_store::store_path::{ParseStorePathError, StorePath, STORE_DIR};
@@ -18,7 +19,7 @@ pub struct Derivation {
     pub environment: BTreeMap<String, String>,
 
     #[serde(rename = "inputDrvs")]
-    pub input_derivations: BTreeMap<String, Vec<String>>,
+    pub input_derivations: BTreeMap<String, BTreeSet<String>>,
 
     #[serde(rename = "inputSrcs")]
     pub input_sources: Vec<String>,
@@ -173,13 +174,14 @@ impl Derivation {
                 hasher.finalize()
             }
             None => {
-                let mut replaced_input_derivations: BTreeMap<String, Vec<String>> = BTreeMap::new();
+                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.to_vec(),
+                        input_derivation.clone(),
                     );
                 }